# GATEBOOK_DS_1_12_Asymptotic_Notations

133 views
Which of the following is the correct order if they are ordered by asymptotic growth rates?

$F_1:n^{lg\,lgn}$

$F_2:(3/2)^n$

$F_3:(lg\,n)^{lg\, n}$

$F_4:n!$

$F_3$ can be re-written as $n^{lg\,lgn}$ using property $a^{log_bc}=c^{log_ba}$

So, $F_4 \gt F_2 \gt F_1=F_3$

Is my order correct?
0
How would you decide between $F_2$ and $F_3$?
1
Ayush your order is spot on.

@srestha F4 comes first, followed by F2, not the other way around. Comment below in case you need explanation.
1
yes, got it
0
@Ayush
0
one is power of log n

and another is power of n

So, power of n will be greater
0
Yes, but one is constant to some power and the other is a variable.

How do you decide then?
1
@goxul-$F_2$ is exponential and $F_3$ is polynomial. Exponential grow faster than polynomial

## Related questions

1
245 views
What is the running time of the following function (specified as a function of the input value)? void Function(int n){ int i=1; int s=1; while(s<=n){ i++; s=s+i; } } $O(n)$ $O(n^2)$ $O(1)$ $O(\sqrt n)$
The asymptotic upper bound solution of the recurrence relation given by $T(n)=2T \left ( \frac{n}{2} \right)+\frac{n}{\lg n}$ is: $O(n^{2})$ $O(n \lg n)$ $O(n \lg \lg n)$ $O(\lg \lg n)$
Among the following asymptotic expressions, which of these functions grows the slowest (as a function of $n$) asymptotically? $2^{\log n}$ $n^{10}$ $(\sqrt{\log n})^{\log ^{2} n}$ $(\log n)^{\sqrt{\log n}}$ $2^{2^{\sqrt{\log\log n}}}$
Obtain asymptotically tight bounds on $lg\ (n!)$ without using Stirling’s approximation. Instead, evaluate the summation $\sum_{k=1}^{n} lg\ k$.