Class Notes (837,539)
Canada (510,303)
CSC104H1 (67)
Lecture 20

Lecture 20 - Algorithm Efficiency

2 Pages
Unlock Document

Computer Science
Mark Lanctot

Algorithm Complexity – Lecture 20 G(n) is order f(n) G(n) is O(f(n)) The function inside the of is a “Bounding Function”. G(n) never grows faster than f(n). In computer science, we group these functions into classes/families. Exponential O(2^n), O(3^n)… Polynomial O(n^2), O(n^3)… LogLinear O(n log(n) ) Linear O(n) Logarithmic O(log(n)) Constant O(1) Properties  If g(n) is O(f(n)) and f(n) is O(h(n)) o G(n) is O(h(n))  Eg, g(n) = 3n  F(n) = 17n  H(n) = 18n - n  NEEDS MORE STUFF HERE  If g1(n) is O(f1(n)), g2(n) is O(f2(n)) o Then g1(n) + g2(n) is  O(f1(n)+f2(n))  If g1(n) is O(f1(n)), g2(n) is O(f2(n)) o Then g1(n) * g2(n) is  O(f1(n)*f2(n))  If k is a constant and g(n) is O(k*f(n)) o Then g(n) is O(f(n)) o Eg. 18000000000n^2 is O(n^2)  O(log(n)) assumes log base 2, but… o O(log base k n) = O( ) = O( ) = O(c * log base 2 n) =
More Less

Related notes for CSC104H1

Log In


Join OneClass

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

Sign up

Join to view


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.