CS137 Lecture Notes - Lecture 17: Big O Notation, Polynomial, Linear Search

• School: University of Waterloo
• Department: Computer Science
• Course: CS137
• Professor: Andrew Morton

Document Summary

Let f(x) be a function over real numbers. G(x) o(f(x)) if and only if there exists m>0 and x0 such that |g(x0| m|f(x)| for all x>x0. Eg: 3x2 + 2 o(x2) If x>1, then |3x2 + 2| = 3x2 5x2 = 5|x2: 5 is m, x2 is f(x) |3x2 + 2| m|x2| for all x>x0: constant: 6sinx o(1) If x>0, then |6sinx| 6: 6=m f(x)=1, polynomial: g(x) is any polynomial. G(x) = anxn + an-1xn-1 + + a1. If x>1, then | anxn + an-1xn-1 + + a1| |an|xn + |an-1|xn-1 + + |a1| As a result, if n m then xn o(xm: eg: x4 o(x76, logarithmic: logax o(logbx) If x>1 then |loga(x)| = loga(x) = logb(x) / logb(a) = |logb(x)| / logb(a) We can ignore the base of the logarithm: transitivity: if h(x) o(g(x)) and g(x) o(f(x)) H(x) o(f(x): exponential: xn o(cx)