Class Notes (922,111)
CA (542,723)
UTSC (32,892)
CSCA67H3 (57)
Lecture

Time Complexity and running time of algorithms

27 Pages
194 Views

Department
Computer Science
Course Code
CSCA67H3
Professor
Richard Pancer

This preview shows pages 1-3. Sign up to view the full 27 pages of the document.
Running time of Algorithms
Q.What is astep?
Conventions wewill use.
method call 1+steps to evaluate each argument +steps
to execute method
return statement 1+steps to evaluate returnvalue
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 operators1+steps to
evaluate each operand
arrayaccess 1+steps to evaluate index
member access 2steps
constants, variables 1step
1
www.notesolution.com
Example.Insertion Sort
Precondition. Ais an arrayof integers.
Postcondition Asorted 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.
tIS(A)is the number of steps or time for IS to run on a
specific input A.
TIS(n)is the worst case time for anyinput of sizen.
2
www.notesolution.com
Q.Whymight weprefer TIS(n)to tIS(A)?
because it is much more general.
Q.Whymight computing TIS(n)be difficult?
Wehaveto consider all possible inputs of sizen.
Solution. Wefind upper and lower bounds for TIS (n).
Q.What do wemean byan upper bound for TIS (n)?
The max number of steps that the code can make.
Q.What do wemean byalower bound for TIS (n)?
Wewant the maximum number of steps that an input will force.
Note.
No input can takemore steps than the upper bound.
Alower bound cannot takeless steps than anyinput.
3
www.notesolution.com

Loved by over 2.2 million students

Over 90% improved by at least one letter grade.

Leah — University of Toronto

OneClass has been such a huge help in my studies at UofT especially since I am a transfer student. OneClass is the study buddy I never had before and definitely gives me the extra push to get from a B to an A!

Leah — University of Toronto
Saarim — University of Michigan

Balancing social life With academics can be difficult, that is why I'm so glad that OneClass is out there where I can find the top notes for all of my classes. Now I can be the all-star student I want to be.

Saarim — University of Michigan
Jenna — University of Wisconsin

As a college student living on a college budget, I love how easy it is to earn gift cards just by submitting my notes.

Jenna — University of Wisconsin
Anne — University of California

OneClass has allowed me to catch up with my most difficult course! #lifesaver

Anne — University of California
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
Unlock Document


Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

Unlock Document
You're Reading a Preview

Unlock to view full version

Unlock Document

Log In


OR

Don't have an account?

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