# Asymptotics.

• Apr 21st 2010, 12:15 PM
zhupolongjoe
Asymptotics.
I'm trying to order some numbers....For n very large, I need to order:

2^n, 4^n, 2^(n^2), n!, and n^n

I know 2^n<4^n<n^n, but I'm not sure where the 2^(n^2) and the n! come in...I want to say it goes 2^n<4^n<2^(n^2)<n!<n^n, but I'm not too sure.

Is this correct?
• Apr 21st 2010, 03:20 PM
TKHunny
Logarithms will buy you the first three.

$n\cdot log(2)$

$2n\cdot log(2)$

$n^{2}\cdot log(2)$

That is now rather easy to order.

$2^{n}\;<\;4^{n}\;<\;2^{n^{2}}$

The last to are easy enough by themselves. One is n factors of n and the other is n factors, but only the largest is as great as n.

$n!\;<\;n^{n}$

Two logs will settle everything but the factorial. You do that.

All we've left is the factorial vs. the $2^{n^{2}}$

No ideas? Search the brain.

Note: The log is useful because it is monotonic increasing. This is a useful transformation that does not change the order of anything.
• Apr 21st 2010, 05:44 PM
zhupolongjoe
Actually, I think I have it. 2^(n^2) is the biggest of all of them since 2^(n^2)=2^(n*n)=(2^n)^n, which is larger than n^n.
• Apr 21st 2010, 07:25 PM
TKHunny
$n^{2} \cdot log(2)$

$2\cdot log(n) + log(log(2))$

vs.

$n \cdot log(n)$

$log(n) + log(log(n))$

Determination:

$log() >> log(log()),$so essentially, we have $2 \cdot log(n) > log(n)$ and I think you have it. (But I am still a little worried about just how big 'n' is.)