5 / 5 Asymptotic Notation & Growth

Race At One Million

Rank these four functions from smallest to largest at n=220=1,048,576n = 2^{20} = 1{,}048{,}576. Two rows are filled in for you.

function value at n=220n = 2^{20}
nlog⁡2nn \log_2 n ?
n1.5n^{1.5} ?
2log⁡2n2^{\log_2 n} 1.05×1061.05 \times 10^6
nlog⁡2log⁡2nn \log_2 \log_2 n 4.53×1064.53 \times 10^6
A

nlog⁡2log⁡2n<2log⁡2n<n1.5<nlog⁡2nn\log_2\log_2 n < 2^{\log_2 n} < n^{1.5} < n\log_2 n

B

2log⁡2n<nlog⁡2log⁡2n<nlog⁡2n<n1.52^{\log_2 n} < n \log_2\log_2 n < n\log_2 n < n^{1.5}

C

2log⁡2n<nlog⁡2log⁡2n<n1.5<nlog⁡2n2^{\log_2 n} < n\log_2\log_2 n < n^{1.5} < n\log_2 n

D

2log⁡2n<nlog⁡2n<nlog⁡2log⁡2n<n1.52^{\log_2 n} < n\log_2 n < n\log_2\log_2 n < n^{1.5}