edited by
4,581 views
9 votes
9 votes

Among the following asymptotic expressions, which of these functions grows the slowest (as a function of $n$) asymptotically?

  1. $2^{\log n}$
  2. $n^{10}$
  3. $(\sqrt{\log n})^{\log ^{2} n}$
  4. $(\log n)^{\sqrt{\log n}}$
  5. $2^{2^{\sqrt{\log\log n}}}$
edited by

4 Answers

5 votes
5 votes

For simplicity, considering log with base $2$.

$f_1 = 2^{\lg n}\; =\; n^{\lg 2}$

$f_2= n^{10}$

So, $f_1$ has slower growth rate than $f_2$ i.e.

--- $f_1 << f_2$

$f_3 = (\sqrt{\lg n})^{\lg^2n} =(\lg n)^{\frac{\lg ^{2}n}{2}} = (\lg n)^{\frac{(\lg n)^2}{2}}$

$f_4 = (\lg n)^{\sqrt{\lg n}} = (\lg n)^{(\lg n)^{\frac{1}{2}}}$

$\because$ $(\lg n)^{\frac{1}{2}} < \frac{(\lg n)^2}{2}.$ (For large values of $'n'$). So,

--- $f_4 << f_3.$

Between $f_1$ and $f_4 :$

$f_4$ can be rewritten as $2^{\lg \; ((\lg n)^{\sqrt{\lg n}})}= 2^{\sqrt{\lg n}\;\lg \lg n}$

So, comparison is between $2^{\lg n}$ and $2^{\sqrt{\lg n}\;\lg \lg n}$

$\because$ $\lg n > \sqrt{\lg n}\;\lg \lg n$ ( $\sqrt{\lg n}$ is common in both functions). So,

--- $f_4 << f_1.$

Till now, among $f_1,f_2,f_3,f_4$, slowest function is $f_4$. If we get $f_5 << f_4$ then $f_5$ will be slowest otherwise $f_4.$

Between $f_4$ and $f_5 :$

$f_5 = 2^{2^{\sqrt{lglgn}}} $

$f_4$  can also be rewritten as $2^{2^{\lg (\sqrt{\lg n}\;\lg \lg n)})}$ 

Now, $\lg (\sqrt{\lg n}\;\lg \lg n) =\lg \sqrt{\lg n} + \lg \lg \lg n = \frac{1}{2} \lg \lg n + \lg \lg \lg n  > \sqrt{\lg \lg n}.$

--  $f_5 << f_4.$

Hence, function $f_5$ grows slowest asymptotically.

Now, to get the correct order, we have to compare  $f_2$ and $f_3.$

Between $f_2$ and $f_3 :$

set $n=2^m$

$f_2 =  (2^{m})^{10}$

$f_3 = m^{\frac{m^2}{2}} = (m^m)^{m/2}$

Since, $m^m >> m! >> 2^m.$ So,

--  $f_2 << f_3.$

Or, we can do like this :

$f_2 = n^{10} = 2^ {\lg n^{10}} = 2^{10 \lg n}$

$f_3 = (\lg n)^{\frac{(\lg n)^2}{2}} = 2^{\lg ( (\lg n)^{\frac{(\lg n)^2}{2}})} = 2^{\frac{(\lg n)^2}{2} \lg \lg n}$

$\because  10 \lg n < \frac{(\lg n)^2}{2} \lg \lg n.$ So, $f_2 << f_3.$

Therefore, increasing order of growth rate is :

$f_5 << f_4 << f_1 << f_2 << f_3$

edited by
4 votes
4 votes

For larger value of $n$ Option E) grows slowest


Put $n=2^{64}$

$A)$ $2^{log n}= 2^{64}$

$B)$ $n^{10}= 2^{640}$

$C)$ $(√log n)^{log^2 n}= 8^{64*64}= 2^{3*64*64}=2^{12288}$

$D)$ $(log n)^{√log n}= 64^{√8} = 2^{6√8}= 2^{16.97}$

$E)$ $2^{2^{√log log n}}= 2^{2^{√8}}=2^{7.10}$

1 votes
1 votes

The quickest way to solve this is by choosing a very large value of n (preferably a power of 2 with log base 2). This is efficient and accurate since it takes less time to analyze the options and it solves for all values of $n\geq n_{0}$.

The correct option is E.

0 votes
0 votes
putting n=32 we can show that the assymptotic expressionin option E is the slowest growing function.
Answer:

Related questions

1 votes
1 votes
2 answers
3
admin asked Feb 10, 2020
2,137 views
In a certain year, there were exactly four Fridays and exactly four Mondays in January. On what day of the week did the $20^{th}$ of the January fall that year (recall th...