Take the following list of functions and arrange them in ascending order of growth rate. That is, if function g(n) immediately follows function f(n) in your list, then it should be the case that f(n) is O(g(n)).



g1(n) = 2√log n
g2(n) = 2n
g4(n) = n4/3
g3(n) = n(log n)3
g5(n) = nlog n
g6(n) = 2^(2^n )
g7(n) = 2^(n^2 )

Solution:

We can put g2, g6 and g7 end of the list, because these functions are exponential and will grow faster.

*g1 is slower than g3
2√log n = √log n log2
log n (log n)3 = log n + 3logn

*g3 grows slower than g4. When we divide both side by 3 and there are log n3 against n1/3. Then (log n)3 < n1/3 *g4 grows slower than g5, n4/3< nlog n when n means to infinity. *g5 grows slower than g2, nlog n<2n as I said in the beginning the g2 is exponential and will grow faster.

*g2 grows slower than g7, 2n<2^(n^2 ) * g7 grows slower than g6, 2^(n^2 )< 2^(2^n ) The correct order is g1,g3,g4,g5,g2,g7,g6.