Register

UPPCL AE 2018:38

• edited by
461 views
0 votes
0 votes

 

Which of the given options provides the increasing order of asymptotic complexity of functions $\text{f}_{1}, \text{f}_{2}, \text{f}_{3}$ and $ \text{f}_{4} $ ?

$\text{f}_{1} = 2^{n}, \qquad \text{f}_{2} = n^{\lg n}, \qquad \text{f}_{3} = n^{\sqrt{n}}, \qquad \text{f}_{4} = n^{2}$

  1. $\text{f}_{2}, \text{f}_{3}, \text{f}_{1}, \text{f}_{4}$
  2. $\text{f}_{4}, \text{f}_{2}, \text{f}_{3}, \text{f}_{1}$
  3. $\text{f}_{3}, \text{f}_{2}, \text{f}_{1}, \text{f}_{4}$
  4. $\text{f}_{4}, \text{f}_{3}, \text{f}_{2}, \text{f}_{1}$
• edited by
User Avatar

1 Answer

0 votes
0 votes

$ f1=2^n, f2=n^(logn)  ,     f3=n^√n  ,    f4=n^2  $

lets check for large value of n i.e $2^6$

$f1=2^(64),  f2=(2^5)^6,   f3=(2^6)^8,   f4=(2^(12)) $

$f1= 2^(64),f2=2^(30) f3=,2^(48),f4=2^(12) $

Increasing Order of Asymptotic complexity:

f4<f2<f3<f1

Hence B is the correct option.

User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
1
admin asked Jan 5, 2019
298 views
UPPCL AE 2018:72
The recurrence equation $T(n) = T(\sqrt{n}) + O(1)$ has the following asymptotic solution: $T(n) = O(\sqrt{n})$ $T(n) = O(\log n)$ $T(n) = O(n^{1/\log n})$ $T(n) = O(\log \log n)$
The recurrence equation $T(n) = T(\sqrt{n}) + O(1)$ has the following asymptotic solution:$T(n) = O(\sqrt{n})$$T(n) = O(\log n)$$T(n) = O(n^{1/\log n})$$T(n) = O(\log \lo...
User Avatar
0 votes
0 votes
1 answer
2
admin asked Jan 5, 2019
404 views
UPPCL AE 2018:55
An unordered list contains $n$ distinct elements. The number of comparisons to find an element in the list that is larger than the second minimum in the list is $\Theta(n \log n)$ $\Theta(n/ \log n)$ $\Theta(1)$ $\Theta(\log n)$
An unordered list contains $n$ distinct elements. The number of comparisons to find an element in the list that is larger than the second minimum in the list is$\Theta(n ...
User Avatar
0 votes
0 votes
1 answer
3
admin asked Jan 5, 2019
310 views
UPPCL AE 2018:23
Consider the following code snippet. It accepts a positive integer $n$ as input. int i = 0, j = 0, val = 1; for(i = 1; i <= n; i++) { j = n; if (i%2 == 0) { while(j>1) { val = val * j; j = j / 2; } } } What is the worst-case time complexity of the algorithm? $O(n)$ $O(n^{2})$ $O(n^{2} \log n)$ $O (n \log n)$
Consider the following code snippet. It accepts a positive integer $n$ as input.int i = 0, j = 0, val = 1; for(i = 1; i <= n; i++) { j = n; if (i%2 == 0) { while(j>1) { v...
User Avatar
0 votes
0 votes
0 answers
4
admin asked Jan 5, 2019
221 views
UPPCL AE 2018:56
The Adjacency matrix of a directed graph $\text{G}$ ... $(h, c, a, e, f, d, i, g, b)$ $(c, a, d, e, f, g, h, i, b)$
The Adjacency matrix of a directed graph $\text{G}$ is given below.$\begin{array} {} & a & b & c & d & e & f & g & h & i \\ a & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ b & ...
User Avatar
Link Copied!