Class Notes (835,384)
CSCA67H3 (56)
Lecture

# Time Complexity and running time of algorithms

27 Pages
194 Views

Department
Computer Science
Course
CSCA67H3
Professor
Richard Pancer
Semester
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
Me

OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.