Asymptotic Notation

• $O$-, $\Theta$-, and $\Omega$- notations.
• Big-theta and big-omega notations are advocated by Knuth to correct the practice of using big-oh for both upper and lower bound.
• All functions must be asymptotically nonnegative, i.e. nonnegative when $n$ large enough.
• When asymptotic notations are on the right side, the equal sign means membership
• We can say:
  • The worst-case running time of insertions sort is $\Theta (n^2)$, or $O(n^2)$
  • The running time of insertion sort is $O(n^2)$
• We cannot say: The running time of insertion sort is $\Theta (n^2)$. Since the best-case time is $\Theta (n)$