Time Complexity and running time of algorithms

27 Pages
194 Views
Unlock Document

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 specific 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 difficult? We have to consider all possible inputs of size n. Solution. We find 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 Definitions “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. Definitions. 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

Log In


OR

Join OneClass

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

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
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.

Add your courses

Get notes from the top students in your class.


Submit