Class Notes
(808,131)

Canada
(493,086)

University of Toronto Scarborough
(30,806)

Computer Science
(300)

CSCA67H3
(56)

Richard Pancer
(3)

Lecture

# Time Complexity and running time of algorithms

Unlock Document

University of Toronto Scarborough

Computer Science

CSCA67H3

Richard Pancer

Winter

Description

Running time of Algorithms
Q. What is a step?
Conventions we will use.
• method call 1 + steps to evaluate each argument + steps
to execute method
• return statement 1 + steps to evaluate return value
• if statement, while statement (not the entire loop) 1 +
steps to evaluate exit condition
• assignment statement 1 + steps to evaluate each side
• arithmetic, comparison, boolean operators 1 + steps to
evaluate each operand
• array access 1 + steps to evaluate index
• member access 2 steps
• constants, variables 1 step
1
www.notesolution.com Example. Insertion Sort
Precondition. A is an array of integers.
Postcondition A sorted in non-decreasing order.
IS (int[] A){
int i = 1 // 1: steps
while (i < A.length()){ // 2: steps
t = A[i]; // 3: steps
int j = i; // 4: steps
while (j > 0 && A[j-1] > t){ // 5: steps
A[j] = A[j-1]; // 6: steps
j = j-1; // 7: steps
}
A[j] = t; // 8: steps
i = i+1; // 9: steps
}
}
Notation.
• t (A) is the number of steps or time for IS to run on a
IS
speciﬁc inpuA.
• TISn) is the worst case time for any input of size n.
2
www.notesolution.com Q. Why might we prefer TISn) to tISA)?
because it is much more general.
Q. Why might computing T IS) be difﬁcult?
We have to consider all possible inputs of size n.
Solution. We ﬁnd upper and lower bounds for T ISn ).
Q. What do we mean by an upper bound for T ISn )?
The max number of steps that the code can make.
Q. What do we mean by a lower bound for T IS(n)?
We want the maximum number of steps that an input will force.
Note.
• No input can take more steps than the upper bound.
• A lower bound cannot take less steps than any input.
3
www.notesolution.com Finding an Upper Bound
IS (int[] A){
int i = 1 // 1: < steps
while (i < A.length()){ // 2: < steps
t = A[i]; // 3: < steps
int j = i; // 4: < steps
while (j > 0 && A[j-1] > t){ // 5: < steps
A[j] = A[j-1]; // 6: < steps
j = j-1; // 7: < steps
}
A[j] = t; // 8: < steps
i = i+1; // 9: < steps
}
}
Q. At most how many steps do lines 5-7 execute?
A.length() times the number of steps, so nx + the loop test y.
Q. At most how many steps do lines 2-9 take?
Loops n times, so n(nx + y + z) where z are the number of
steps in lines 2-4, 8, 9 plus the loop test.
Q. What is an upper bound then?
cn2
Q. Does it matter what the constant is?
no.
4
www.notesolution.com A Lower Bound
Goal. Show that in the worst case,IS(n ) will take at least f(n)
steps.
IS (int[] A){
int i = 1 // 1: >1 step
while (i < A.length()){ // 2: >1 step
t = A[i]; // 3: >1 step
int j = i; // 4: >1 step
while (j > 0 && A[j-1] > t){ // 5: >1 step
A[j] = A[j-1]; // 6: >1 step
j = j-1; // 7: >1 step
}
A[j] = t; // 8: >1 step
i = i+1; // 9: >1 step
}
}
Q. Which input forces the greatest number of steps?
An array A of length n sorted in decreasing order, ie, {n−1,n−
2,n − 3,... ,n − i,...2,1,0}
Computing the number of steps.
m A[0..m] after outer loop inner loop steps
0 n-1 0
1 n-2,n-1 loops 1 time, so ≥ 1 ▯ 3+1 for exit
2 n-3,n-2,n-1 loops 2 times, so ≥ 2 ▯ 3 + 1
3 n-4,n-3,n-2,n-1 loops 3 times, so ≥ 3 ▯ 3 + 1
. . .
k n-k-1, n-k, n-k+1, ... , n-1 loops k times, so ≥ k ▯ 3 + 1
. . .
. . .
n-1 1,2,3, ... , n-1 ≥ (n − 1)(3) + 1
5
www.notesolution.com Q. At least how many steps does IS(A) take?
sum the above lines adding 5 per outer loop iteration.
X−1 X−1 X−1
i ∗ 3 + 1 = 3 i + 1
i=1 i=1 i=1
(n − 1)(n − 2) 3 9 3 7
= 3 + n − 1 = n − n + 3 + n − 1 = n − n +
2 2 2 2 2
Q. Which term is the most important?
n2
Q. Why do we only care about this term?
2
because as n gets big, n gets much bigger thant just n.
Q. What do we notice about the upper and lower bounds?
the same function of n, n .
This is called a tight bound because the upper and lower bounds
are the same function of n.
6
www.notesolution.com Formal Deﬁnitions
“Big Oh” – The Upper Bound
Idea. Want a function g(n) such that for
• BIG enough n ,
• T (n) ≤ c▯g (n)
• where c is a constant.
Deﬁnitions.
R +: the set of positive, real numbers.
+
R 0: the set of positive, real numbe0s.≥
N : the set of natural numbersk.
k
+
F: the set of functionsf :N k→ R0 }.
7
www.notesolution.com “Big Oh.” Letg ∈ F. O( g) is the set of functions f ∈ F such
that
∃c ∈ R +,∃b ∈ N,∀n ∈ N ,n ≥ b → f(n) ≤ c ▯ g(n)
∗
Pictorally :
Example. Consider IS(A). We showed that:
T IS) ≤ xn + (y + z)n + w,∀n ≥ 1
Q. For which function g(n) doTsISn) ∈ O( g(n))?
g(n) = n 2
Q. Why?
2 2 2 2
Notice that xn + (y + z)n + w ≤ xn + (y + z)n + wn for
n ≥ 1. Therefore, let c = (x + y + z + w) and b = 1. Then
∃c ∈ R+ ,∃b ∈N ,∀n ∈ N,n ≥ b → T IS) ≤ cn .2
∗Figure 2.1 in Introduction to Algorithms
8
www.notesolution.com “Big–Oh”
Example. Letf n ) = n3− n 2+ 5 .
Q. What should g(n) be such thf(n) ∈ O(g(n ))?
3
n
Proof – Rough Work.
n − n + 5 ≤ n + 5
3 3
≤ n + 5n
= 6n 3
Q. What isb?
3 3 3
For n + 5 ≤ n + 5n we need b ≥ 1, so let b = 1.
Q. What isc?
c=6.
Formal Proof.
Claim.
+ 3 2 3
∃c ∈ R ,∃b ∈N,∀n ∈ N ,n ≥ b → (n − n + 5 ≤ c ▯ n )
9
www.notesolution.com Proof. ∃c ∈R+,∃b ∈ N,∀n ∈ N ,n ≥ b → (n −n +5 ≤ c▯n )
Let c = 6, then cR∈+.
Let b = 1, then bN.
Let n ∈N .
Suppose n ≥ 1.
Then
3 3 3
6n = n + 5n
≥ n − n + 5n 3
3 2
≥ n − n + 5 since n ≥ 1.
Hence n − n + 5 ≤ 6n 3
3 2 3
Since n ≥ 1, n ≥ 1 → n − n + 5 ≤ 6n .
Since n ∈ N and n is arbitrary,
∀n ∈ N,n ≥ 1 → n − n + 5 ≤ 6n 3
Since b = 1,b ∈N,
3 2 3
∃b ∈N ,∀n ∈N ,n ≥ b → n − n + 5 ≤ 6n
+
Since c = 6,c ∈R ,
+ 3 2 3
∃c ∈R ,∃b ∈N ,∀n ∈ N,n ≥ b → n − n + 5 ≤ 6n
10
www.notesolution.com “Big Omega” – The Lower Bound
Idea. Want a function g(n) such that for
• BIG enough n,
• T(n ) ≥ d▯g (n)
• where d is a constant.
“Big Omega.” Let g∈ F. Ω( g) is the set of functions f ∈ F
such that
+
∃d ∈ R ,∃b ∈ N ,∀n ∈ N,n ≥ b → f(n) ≥ d ▯ g(n)
∗
Pictorally :
∗
Figure 2.1 in Introduction to Algorithms
11
www.notesolution.com “Big–Omega”
3 2
Example. Let f(n) = n − n + 5.
Q. What should g(n) be such thf(n ) ∈ O(g(n))?
n3
Proof – Rough Work.
3 2 3 2
n − n + 5 > n − n
≥ ??
Consider n − n ≥ dn :3
n − n 2 ≥ dn 3
n − 1 ≥ dn
(n − dn) ≥ 1
n(1 − d) ≥ 1
1
n ≥
(1 − d)
Q. What should we selecd to be?
Notice that in order for n ≥ b wherZ we should pick d < 1.
For example, let d = .
2
Q. What then, ib?
b = 2.
12
www.notesolution.com Formal Proof.
Claim.
+ 3 2 3
∃d ∈R ,∃b ∈N ,∀n ∈N,n ≥ b → (n − n + 5 ≥ d ▯

More
Less
Related notes for CSCA67H3