# 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)$