Asymptotic growth

[iori]

Hi guys, I have been asked order the following function by asymptotic growth rate

lgn, lg*n, n2, n3, lnlnn, [(lgn) pow 1/2], lg(lg*n), lg*(lgn), n! , (2 pow n),
[2 pow (2n+1)], (n+1)!

My Ans: lg(lg*n), lg*(lgn), lg*n, [(lgn) pow 1/2] , lnlnn, lgn, (2 pow n),
[2 pow (2n+1)], n2, n3, n!, (n+1)!

Is that correct, if not please correct it for me. Thank you.

[RoboTact]

Check 2^n vs. n^2.

[TomWidmer]

Your notation is new to me. What's the difference between lgn and lg*n?

[iori]

Check 2^n vs. n^2.

Thanks for pointing that one out..

I have re-calculated and here is the result...

lg(lg*n), lg*(lgn) , lnlnn , (lgn)^1/2 , lg*n, lgn , n^2 , 2^n , n^3 , 2^(2n+1),
n! , (n+1)!

Any error ?

Mate, I have another question..

Is 2^(n+1) = O(2^n) ?
and 2^(2n) = O(2^n) ?

I can undersatnd it when the power in on n, but I don't get it when the power is on a constant.

------

@TomWidmer Sorry but I do not have a clear understanding of that either.

I can give you some examples though..

lg*4 = 2
lg*8 = 3
lg*16 = 3

(all logarithm are of base 2)

[Tom Frohman]

Is 2^(n+1) = O(2^n) ?
and 2^(2n) = O(2^n) ?




limit 2^(n+1)/2^n as n->inf=2 so 2^(n+1) IS of O(2^n) i.e. we can find a constant C such that |2^(n+1)|<=C|2^n| for all n. The constant here being 2.

limit 2^(2n)/2^n=2^n as n->inf=inf so 2^(2n) IS NOT O(2^n) as there is no constant C such that |2^(2n)|<=C|2^n| for all n

[iori]

Thanks for the explanation Tom. :)