GATE 2024 CS (CS1) – Question 42

Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · Multiple choice

Consider the recurrence $T(n)=\sqrt{n}\,T(\sqrt{n})+n$ for $n\ge 1$... with $T(1)=1$. Which one of the following options is CORRECT?

$T(n)=\Theta(n\log\log n)$
$T(n)=\Theta(n\log n)$
$T(n)=\Theta(n^2\log n)$
$T(n)=\Theta(n^2\log\log n)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $T(n)=\Theta(n\log\log n)$

Explanation

Let $T(n)=nS(n)$: $S(n)=S(\sqrt{n})+1$. This gives $S(n)=\Theta(\log\log n)$, so $T(n)=\Theta(n\log\log n)$.