The GATE Grind

GATE 2021 CS – Question 40

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

Consider the following recurrence relation.
$T(n) = T(n/2) + T(2n/5) + 7n$ if $n>0$; $T(n)=1$ if $n=0$.
Which one of the following options is correct?

  1. $T(n) = \Theta(n^{5/2})$
  2. $T(n) = \Theta(n \log n)$
  3. $T(n) = \Theta(n)$
  4. $T(n) = \Theta((\log n)^{5/2})$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $T(n) = \Theta(n)$

Explanation

Subproblem sizes sum to n/2 + 2n/5 = 9n/10 < n, so the work per level shrinks geometrically. The root's 7n dominates, giving $\Theta(n)$.