GATE 2024 CS1 Q.42: solution and answer

GATE 2024 · CS1Q.42 · 2 marks · MCQ

Consider the following recurrence relation:

T (n) = {n T (n) + n 1 for n \geq 1, for n = 1.

Which one of the following options is CORRECT?

(A)
$T (n) = Θ (n lo g lo g n)$
(B)
$T (n) = Θ (n lo g n)$
(C)
$T (n) = Θ (n^{2} lo g n)$
(D)
$T (n) = Θ (n^{2} lo g lo g n)$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

T(n) = Θ(n log log n) — option (A).

Official answer: ASource: Official answer key, GATE 2024 CS1 (IISc Bengaluru)

Substitute $n = 2^{m}$ , so $S (m) := T (2^{m}) = T (n)$ , and $n = 2^{m /2}$ , so $T (n) = S (m /2)$ .
The recurrence $T (n) = n T (n) + n$ becomes $S (m) = 2^{m /2} S (m /2) + 2^{m}$ .
Divide both sides by $2^{m}$ : $\frac{S ( m )}{2 ^{m}} = \frac{S ( m /2 )}{2 ^{m /2}} + 1$ . Let $R (m) := S (m) / 2^{m}$ ; then $R (m) = R (m /2) + 1$ .
This is a Master-theorem case with $a = 1$ , $b = 2$ , $f (m) = Θ (1)$ : since $lo g_{b} a = 0$ matches the degree of $f (m)$ , $R (m) = Θ (lo g m)$ .
So $S (m) = 2^{m} \cdot Θ (lo g m)$ . Since $m = lo g n$ and $2^{m} = n$ , this gives $T (n) = n \cdot Θ (lo g (lo g n)) = Θ (n lo g lo g n)$ .
This matches option (A).

KEY IDEA

A recurrence with a $n$ argument is solved by the double substitution $n = 2^{m}$ (turning $n$ into a halving of $m$ ), then dividing through by the multiplicative factor $2^{m /2}$ so the recurrence becomes a plain additive one in $m$ , solvable directly or via the Master theorem.

WATCH OUT FOR

Stopping after finding $T (n) = n \cdot Θ (lo g m)$ and forgetting to re-substitute $m = lo g n$ into the $n$ -side, so students report $Θ (n lo g n)$ (option B) instead of correctly reducing $lo g m = lo g (lo g n)$ to get $Θ (n lo g lo g n)$ .

From the GATE 2024 CS1 paper. Every question of this paper · Download the full paper · All 14 Complexity questions, with notes

GATE 2024 CS1 Q.42: solution and answer

Answer and solution

More Complexity questions