Exercise XIII
Exercise For each of the $T(n)$ running time listed below, figure out the asymptotic runtime and express it in big Oh notation. Then rank the functions in growth rate order, starting with the slowest growth rate (i.e those resulting in a fast runtime), and ending with the fastest growth rate (worst runtime). If two functions have the same asymptotic runtime, then rank them based on the original expressions (including constants).
| $T(n)$ | Big Oh | Rank |
|---|---|---|
| $\left ( \lg \frac{n}{4} \right )^3$ | ||
| $(n^2-4)/(n+2)$ | ||
| $\left ( 3n + \lg n \right )^2$ | ||
| $2 \lg n^2$ | ||
| $\left ( 2^n \right )^2 + \lg n$ | ||
| $n^2 \lg 16$ | ||
| $2n\lg\lg n$ | ||
| $4n^2+n(10 + \lg n)$ |
Solution
| $T(n)$ | Big Oh | Rank |
|---|---|---|
| $\left ( \lg \frac{n}{4} \right )^3$ | $\left ( \lg n - \lg 4 \right )^3 = \left ( \lg n - 2 \right )^3 \in O(\lg^3 n)$ | 2 |
| $(n^2-4)/(n+2)$ | $(n-2)(n+2)/(n+2) \in O(n)$ | 3 |
| $\left ( 3n + \lg n \right )^2$ | $9n^2+\lg^2 n + 6n\lg n \in O(n^2)$ | 7 |
| $2 \lg n^2$ | $4 \lg n \in O(\lg n)$ | 1 |
| $\left ( 2^n \right )^2 + \lg n$ | $4^n+\lg n \in O(4^n)$ | 8 |
| $n^2 \lg 16$ | $4n^2 \in O(n^2)$ | 5 |
| $2n\lg\lg n$ | $O(n\lg\lg n)$ | 4 |
| $4n^2+n(10 + \lg n)$ | $4n^2+10n+n\lg n \in O(n^2)$ | 6 |
Resources
Logarithmic identities are essential for solving the above exercise.