Arrange the following functions according to the order (rate of growth) from lowest to highest. If any two or more are of the same order, indicate which. (Two functions f, g are of the same order if f = Θ(g);f has order not greater than g if f = O(g).)
NOTE:(ln n stands for the natural logarithm of n and lg n stands for the base-2 logarithm of n.)
$n$
$n^2 + \lg n$
$\lg n$
$\ln \ln n$
$n^2$
$\lg^2 n$
$\ln n$
$n^3$
$n^2 \lg n$
So I think I'm doing this right. Hopefully someone can verify my work..Here is what I have:
1.$n$ = $O(n)$
2.$n^2 + \log n$ = $O(n^2)$
3.$\lg n = O(\lg n)$
4.$\ln \ln n = O(\ln n)$
5.$n^2 = O(n^2)$
6.$\lg^2 n = O(\lg^2 n)$
7.$\ln n = O(\ln n )$
8.$n^3 = O(n^3)$
9.$n^2 \lg n = O(n^2 \lg n)$
So in order from lowest to highest I have:
$\ln n$
$n$
$\lg^2 n$
$n^2$
$n^2 \lg n$
$n^3$