Exercise XIII

  • Rank asymptotic complexities from smallest to largest.

Exercise For each of the T(n)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)T(n)Big-OhRank
(lg⁡n4)3\left ( \lg \frac{n}{4} \right )^3
(n2−4)/(n+2)(n^2-4)/(n+2)
(3n+lg⁡n)2\left ( 3n + \lg n \right )^2
2lg⁡n22 \lg n^2
(2n)2+lg⁡n\left ( 2^n \right )^2 + \lg n
n2lg⁡16n^2 \lg 16
2nlg⁡lg⁡n2n\lg\lg n
4n2+n(10+lg⁡n)4n^2+n(10 + \lg n)
Solution
T(n)T(n)Big-OhRank
(lg⁡n4)3\left ( \lg \frac{n}{4} \right )^3(lg⁡n−lg⁡4)3=(lg⁡n−2)3∈O(lg⁡3n)\left ( \lg n - \lg 4 \right )^3 = \left ( \lg n - 2 \right )^3 \in \Omicron(\lg^3 n)2
(n2−4)/(n+2)(n^2-4)/(n+2)(n−2)(n+2)/(n+2)∈O(n)(n-2)(n+2)/(n+2) \in \Omicron(n)3
(3n+lg⁡n)2\left ( 3n + \lg n \right )^29n2+lg⁡2n+6nlg⁡n∈O(n2)9n^2+\lg^2 n + 6n\lg n \in \Omicron(n^2)7
2lg⁡n22 \lg n^24lg⁡n∈O(lg⁡n)4 \lg n \in \Omicron(\lg n)1
(2n)2+lg⁡n\left ( 2^n \right )^2 + \lg n4n+lg⁡n∈O(4n)4^n+\lg n \in \Omicron(4^n)8
n2lg⁡16n^2 \lg 164n2∈O(n2)4n^2 \in \Omicron(n^2)5
2nlg⁡lg⁡n2n\lg\lg nO(nlg⁡lg⁡n)\Omicron(n\lg\lg n)4
4n2+n(10+lg⁡n)4n^2+n(10 + \lg n)4n2+10n+nlg⁡n∈O(n2)4n^2+10n+n\lg n \in \Omicron(n^2)6
Resources

Logarithmic identities are essential for solving the above exercise.