Skip to content
GATETECH
Official PYQ · 2014Set 2 · Q13Asymptotic Worst Case Time and Space ComplexityMCQ1 mark

GATE CS 2014 Set 2 Q13 — Asymptotic Worst Case Time and Space Complexity

Explain with AI

Which one of the following correctly determines the solution of the recurrence relation with T(1)=1T(1) = 1?

T(n)=2T(n2)+log⁡nT(n)= 2T\left(\frac {n} {2}\right) + \log n

Choose one option
View worked solution

Answer: A

We can solve the given recurrence relation using the Master Theorem:

T(n)=aT(nb)+f(n)T(n) = aT\left(\frac{n}{b}\right) + f(n)

Here, the parameters are:

  • a=2a = 2
  • b=2b = 2
  • f(n)=log⁡nf(n) = \log n

Now, we compare f(n)f(n) with nlog⁡ban^{\log_b a}:

nlog⁡ba=nlog⁡22=n1=nn^{\log_b a} = n^{\log_2 2} = n^1 = n

Since f(n)=log⁡n=O(n1−ϵ)f(n) = \log n = O(n^{1-\epsilon}) for any 0<ϵ<10 < \epsilon < 1, Case 1 of the Master Theorem applies. Therefore, the complexity is dominated by the recursive steps:

T(n)=Θ(nlog⁡ba)=Θ(n)T(n) = \Theta(n^{\log_b a}) = \Theta(n)

Thus, the correct option is A.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Asymptotic Worst Case Time and Space Complexity questions