retagged by
10,006 views
17 votes
17 votes

Consider the following three functions.

$$f_1=10^n\quad f_2=n^{\log n}\quad f_3=n^{\sqrt {n}}$$

Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?

  1. $f_3, f_2, f_1$
  2. $f_2, f_1, f_3$
  3. $f_1, f_2,f_3$
  4. $f_2, f_3, f_1$
retagged by

4 Answers

Best answer
17 votes
17 votes

Lets identify the function types

  • $f_1=10^{n}-$ Exponential Function
  • $f_2=n^{\log n}-$ Super-polynomial but sub-exponential
  • $f_3=n^{\sqrt n}-$ Super-polynomial but sub-exponential 

So, clearly asymptotic growth of $f_1$ is the highest.

Both $f_2$ and $f_3$ are super polynomial (grows faster than any polynomial function) but sub-exponential (grows slower than any exponential function).

Now, $\log n$ grows slower than any power function for positive power (not necessarily a polynomial function). i.e., $\log n = o(n^x), x>0$. So, asymptotic growth of $\log n$ is lower than even $n^{0.000001}.$ $\sqrt n$ is a power function with power $ = 0.5.$ So, clearly $\log n = o(\sqrt n) \implies n^{\log n} = o \left(n^{\sqrt n}\right).$

So, asymptotic growth rate of $f_1,f_2$ and $f_3 $ are in the order $f_2<f_3<f_1.$

Option $D$ is correct.

13 votes
13 votes

Taking $\log$ in $f_1,f_2,f_3$,we get:

  • $f_1=\log(10^{n})\implies n*log10\approx n $
  • $f_2=\log(n^{\log n})\implies\log n*\log n=(\log ^2n)$
  • $f_3=\log(n^{\sqrt n})\implies \sqrt n*\log n$

clearly visible that $f_1$ is polynomial function & $f_2$ is polylogarithmic function.

$\therefore f_2 <f_1$

$f_3 $ is linear log function where $\sqrt n$ is multiplied with $\log n$ function.

so $f_2<f_3<f_1$ is the correct ascending order of growth of the function.

Option $D$ is correct.

Note:  1) Time complexity

           2)  Difference between logarithmic and polylogarithmic function

           3) Same type of concepts asked in:

             GATE IT 2008 | Question: 10

             GATE CSE 2011 | Question: 37,

             GATE CSE 2017 Set 1 | Question: 04

 

 

edited by
5 votes
5 votes

WHENEVER YOU HAVE DOUBT IN WHICH IS GREATER OR WHICH IS LESSER TAKE LOG AND SOLVE IT. 

1 votes
1 votes
F1 is greatest 10^n

Now F2 and F3 is comparison

We know root is greter then log (log 1024 = 10 and √(1,024) =32)

So F3 is greter then F2

Ascending order is f2 < f3 < f1

Answer D is correct
Answer:

Related questions

8 votes
8 votes
3 answers
2
Arjun asked Feb 18, 2021
10,694 views
Consider the following undirected graph with edge weights as shown:The number of minimum-weight spanning trees of the graph is ___________.