false

Class Notes
(835,384)

Canada
(509,147)

University of Toronto Scarborough
(31,452)

Computer Science
(312)

CSCA67H3
(56)

Richard Pancer
(3)

Lecture

by
OneClass8101

Unlock Document

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

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.