General Doubt

Question

Can anyone please explain me the growth rate in terms of decreasing order of values by taking input n as an example?

• $2^{2^{n}}$
• $n!$
• $4^{n}$
• $2^{n}$
• $n^{2}$
• $n log n$
• $log\left ( n!\right )$
• $2^{log n}$
• $log^{2 }n$
• $\sqrt{logn}$
• $log log n$
• 1

Please explain by taking a suitable example.

Comments

you can take log both side and compare 

---

what about $n^{\sqrt{n}}$?

Answer 1

Points used in this

1) n^n has higher order growth than n! reference- https://math.stackexchange.com/questions/674002/which-has-a-higher-order-of-growth-n-or-nn

2) log(n !) = Θ(n·log(n)) reference- https://stackoverflow.com/questions/2095395/is-logn-%CE%98n-logn

​​​​​​​3) n! eventually grows faster than an exponential with a constant base (2^n and e^n), but n^n grows faster than n! since the base grows as n increases. 

now, considering n very large 2$^{1024}$.

1) 1=1.

2)loglog n = log log 2$^{1024}$ = 10.

3)$^{\sqrt{log n}}$ = $\sqrt{log(2^{1024})}$ = 32.

4)log$^{2}n$ =logn*logn= 2$^{10}$ * 2$^{10}$ = 2$^{20}$.

5)2$^{logn}$= 2$^{log 2^{1024}}$ = 2$^{1024}$.

6) log(n!) = $\Theta (nlogn))$= 2$^{1024}$*2$^{10}$ = 2$^{1034}$.

7) nlogn= 2$^{1034}$

8)n$^{2}$ = 2$^{2048}$.

9)2$^{n}$ = 2$^{2^{1024}}$.

10)4$^{n}$=4$^{2^{1024}}$.

11)n! = 2$^{1024}$ !

12)2$^ {2^ {2^ {1024}}}$.

Comments

right, even $\left ( 2^{n^{2}} \right )$ and $\left ( 2^{n} \right )^{2}$ grows differently

---

@ankit that can pe proved easily as

n! can be written as 2^log n!        [ log n! is O(nlogn)]

so, 2^nlogn.

And 2^2^n

By comparing ..obviously 2^n has higher growth rate than nlog n.

So, 2^2^n has higher growth than n!.

---

Thanks Tarun! , actually from limit , I just wanted to prove Limit_{n--> ∞}   (2^{2^n} )/n! = ∞ ..But I did it using L-Hospital Rule..anyway thanks bro..