GATE CS Mastery
Cheat sheets

GATE CS 2011 · Algorithms

Question 37

MCQPrinted as CS Q.372 marksWrong answer: −2/3Medium (estimate)

Question

Which of the given options provides the increasing order of asymptotic complexity of functions f1,f2,f3f_1, f_2, f_3 and f4f_4?

f1(n)=2nf2(n)=n3/2f3(n)=nlog⁡2nf4(n)=nlog⁡2nf_1(n) = 2^n \qquad f_2(n) = n^{3/2} \qquad f_3(n) = n \log_2 n \qquad f_4(n) = n^{\log_2 n}
Choose one option
Official answer and solution
Official answer
A
From
Official GATE 2011 answer key

Solution

Compare asymptotic growth rates using logarithmic transformation.

  1. Take the logarithm log⁡2\log_2 of each function to compare their growth rates:
  • log⁡2f1(n)=log⁡2(2n)=n\log_2 f_1(n) = \log_2(2^n) = n
  • log⁡2f2(n)=log⁡2(n3/2)=1.5log⁡2n\log_2 f_2(n) = \log_2(n^{3/2}) = 1.5 \log_2 n
  • log⁡2f3(n)=log⁡2(nlog⁡2n)=log⁡2n+log⁡2log⁡2n\log_2 f_3(n) = \log_2(n \log_2 n) = \log_2 n + \log_2 \log_2 n
  • log⁡2f4(n)=log⁡2(nlog⁡2n)=(log⁡2n)2\log_2 f_4(n) = \log_2(n^{\log_2 n}) = (\log_2 n)^2
  1. Compare logarithmic growth rates as n→∞n \to \infty:
(log⁡2n+log⁡2log⁡2n)<1.5log⁡2n<(log⁡2n)2<n(\log_2 n + \log_2 \log_2 n) < 1.5 \log_2 n < (\log_2 n)^2 < n
  1. Exponentiating back yields the strict asymptotic hierarchy:
f3(n)<f2(n)<f4(n)<f1(n)f_3(n) < f_2(n) < f_4(n) < f_1(n)
Final answer

A

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2011 Computer Science and Information Technology (CS)
Question
37 of 65, printed as CS Q.37
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.