GATE 2020 CS Q.2: solution and answer

GATE 2020 · CSQ.2 · 1 mark · MCQ

For parameters $a$ and $b$ , both of which are $ω (1)$ , $T (n) = T (n^{1/ a}) + 1$ , and $T (b) = 1$ .

Then $T (n)$ is

(A)
$Θ (lo g_{a} lo g_{b} n)$
(B)
$Θ (lo g_{ab} n)$
(C)
$Θ (lo g_{b} lo g_{a} n)$
(D)
$Θ (lo g_{2} lo g_{2} n)$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

$T (n) = Θ (lo g_{a} lo g_{b} n)$ , so the correct option is (A).

Official answer: ASource: Official answer key, GATE 2020 CS (IIT Delhi)

Let $m = lo g_{b} n$ , so $n = b^{m}$ . We track $S (m) := T (b^{m})$ .
Compute the effect of the recurrence's argument $n^{1/ a}$ under this substitution: $n^{1/ a} = (b^{m})^{1/ a} = b^{m / a}$ , so $lo g_{b} (n^{1/ a}) = m / a$ . Thus $T (n) = T (n^{1/ a}) + 1$ becomes $S (m) = S (m / a) + 1$ .
The base case $T (b) = 1$ corresponds to $m = lo g_{b} b = 1$ , i.e. $S (1) = 1$ .
Unroll directly: $S (m) = S (m / a) + 1 = S (m / a^{2}) + 2 = \dots = S (m / a^{k}) + k$ . This reaches the base case $S (1)$ when $m / a^{k} = 1$ , i.e. $k = lo g_{a} m$ . Hence $S (m) = Θ (lo g_{a} m)$ (no need to invoke the Master theorem, which applies to divide-and-conquer recurrences of the form $T (n) = a T (n / b) + f (n)$ and is not the right tool here; direct unrolling suffices).
Substitute back $m = lo g_{b} n$ : $T (n) = S (lo g_{b} n) = Θ (lo g_{a} (lo g_{b} n)) = Θ (lo g_{a} lo g_{b} n)$ , which is option (A).

KEY IDEA

Substituting $m = lo g_{b} n$ turns the "take a-th root of the argument" recurrence $T (n) = T (n^{1/ a}) + 1$ into the familiar "divide the exponent by $a$ " recurrence $S (m) = S (m / a) + 1$ , whose solution is $Θ (lo g_{a} m)$ ; undoing the substitution gives the nested double logarithm $Θ (lo g_{a} lo g_{b} n)$ .

WATCH OUT FOR

Treating the two parameters $a$ and $b$ as combinable into a single log base (picking option (B), $Θ (lo g_{ab} n)$ ) instead of recognizing that $a$ controls how many times you must take roots (an outer log) while $b$ sets the base at which the argument bottoms out (an inner log) — the two play structurally different roles and cannot be merged into one log base.

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

GATE 2020 CS Q.2: solution and answer

Answer and solution

More Complexity questions