GATE 2021 CS (CS2) – Question 49

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

For constants a≥1,b>1, $T(n)=aT(n/b)+f(n)$. Which general claim is correct, under the usual positive constant base-case assumptions?

$f(n)=n\log_2n\Rightarrow T(n)=\Theta(n\log_2n)$
$f(n)=n/\log_2n\Rightarrow T(n)=\Theta(\log_2n)$
$f(n)=O(n^{\log_ba-\epsilon})$ for some ε>0 implies $T(n)=\Theta(n^{\log_ba})$
$f(n)=\Omega(n^{\log_ba})\Rightarrow T(n)=\Theta(n^{\log_ba})$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $f(n)=O(n^{\log_ba-\epsilon})$ for some ε>0 implies $T(n)=\Theta(n^{\log_ba})$

Explanation

C is the first case of the Master theorem: a polynomially smaller nonrecursive cost leaves the recursion-tree leaf term dominant. A depends on a,b and can acquire extra factors. B cannot hold generally even because its stated f is already larger than logarithmic. D omits both the boundary-case logarithm and the possibility of a much larger f. Thus C.

More Asymptotic Analysis and Time/Space Complexity questions

GATE 2026 CS (CS1) Q17 – Consider the following recurrence relations: For all n > 1: T 1(n) = 4T 1(n/2) + T 2(n) T…
GATE 2026 CS (CS1) Q47 – Let G(V, E) be a simple, undirected graph. A vertex cover of G is a subset V' V such that…
GATE 2026 CS (CS2) Q24 – Consider the following functions, where n is a positive integer: n1/3, n, (n!), and 2 n.…
GATE 2026 CS (CS2) Q25 – Which of the following can be recurrence relation(s) corresponding to an algorithm with…
GATE 2026 CS (CS2) Q38 – Consider an array A of integers of size n with indices from 1 to n. An algorithm is to be…
GATE 2025 CS (CS1) Q20 – Consider the following recurrence relation: T(n) = 2T(n-1) + n2n for n > 0, T(0) = 1.…

All Asymptotic Analysis and Time/Space Complexity questions →