Order of growth of following function

Question

Can someone tell me if the ranking of following functions by order of growth is correct ? (increasing to decreasing)

2^n, n^2, (nlgn, lg(n!)), n^(1/lgn), 4

Answer 1

Most of these are right. However, look at

n^{1/lg n}.

Notice that, for nonzero n, we have n = 2^{lg n}, so

n^{1/lg n} = (2^{lg n})^{1/lg n} = 2^{lg n / lg n} = 2¹ = 2.

So while 2 and 4 do grow at the same (nonexistent) rate, n^{1/lg n} is always smaller than 4 for any nonzero n.