Register

GO Classes DPP | GATE CS, DA | Algorithms | Asymptotic Growth

118 views
2 2 votes

Arrange the following functions in increasing order of asymptotic growth:

$f_1(n) = 2^{2^{1000000}}$

$f_2(n) = 2^{100000n}$

$f_3(n) = {}^{n}C_{2}$

$f_4(n) = n\sqrt n$
 

  1. $f_1(n) < f_4(n) < f_3(n) < f_2(n)$
     
  2. $f_1(n) < f_3(n) < f_4(n) < f_2(n)$
     
  3. $f_4(n) < f_1(n) < f_3(n) < f_2(n)$
     
  4. $f_1(n) < f_4(n) < f_2(n) < f_3(n)$

1 Answer

0 0 votes

The correct order of these functions is $f_1(n)< f_4(n)< f_3(n)< f_2(n)$. 

The variable $n$ never appears in the formula for $f_1(n)$, so despite the multiple exponentials, $f_1(n)$ is constant. 

Hence, it is asymptotically smaller than $f_4(n)$, which does grow with $n$. 

We may rewrite the formula for $f_4(n)$ to be $f_4(n)=n \sqrt{n}=n^{1.5}$. 

The value of $f_3(n)={}^{n}C_{2}$ is given by the formula $n(n-1) / 2$, which is $\Theta\left(n^2\right)$. 

Hence, $f_4(n)=n^{1.5}=O\left(n^2\right)=O\left(f_3(n)\right)$. 

Finally, $f_2(n)$ is exponential, while $f_3(n)$ is quadratic, meaning that $f_3(n)$ is $O\left(f_2(n)\right)$.

Answer : A

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

2 2 votes
1 1 answer
121
121 views
GO Classes asked Jul 29
121 views
GO Classes DPP | GATE CS, DA | Algorithms | Asymptotic Growth
Suppose $f(n) \in \Omega(n^2)$.Classify the following statements:$\text{S1}$. $f(n) \in \Omega(n^3)$ $\text{S2}$. $f(n) \in \Omega(n)$ $\text{S3}$. $f(n) \in O(n)$ $\text...
3 3 votes
1 1 answer
129
129 views
GO Classes asked Jul 29
129 views
GO Classes DPP | GATE CS, DA | Algorithms | Asymptotic Growth
Arrange the following functions in increasing order of asymptotic growth:$f_1(n) = n^{\sqrt n}$$f_2(n) = 2^n$$f_3(n) = n^{10}\cdot 2^{n/2}$$f_4(n) = \sum_{i=1}^{n}(i+1)$ ...
4 4 votes
1 1 answer
156
156 views
GO Classes asked Jul 29
156 views
GO Classes DPP | GATE CS, DA | Algorithms | Asymptotic Growth
Arrange the following functions in increasing order of asymptotic growth:$f_1(n) = \log(n^n)$$f_2(n) = (\log n)^n$$f_3(n) = \log(n^{6006})$$f_4(n) = (\log n)^{6006}$$f_5(...
4 4 votes
1 1 answer
147
147 views
GO Classes asked Jul 29
147 views
GO Classes DPP | GATE CS, DA | Algorithms | Growth Order of Functions
Arrange the following functions in increasing order of asymptotic growth:$f_1(n) = n^{0.999999}\log n$ $f_2(n) = 10000000n$ $f_3(n) = 1.000001^n$ $f_4(n) = n^2$ $f_1(n)< ...