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

GATE CSE 2021 Set 1 Q40: Solve T(n) = T(n/2) + T(2n/5) + 7n

Consider the following recurrence relation.

$T(n) = \begin{cases} T(n/2) + T(2n/5) + 7n & \text{if } n > 0 \\ 1 & \text{if } n = 0 \end{cases}$

Which one of the following options is correct?

Try it: multiple choice: exactly one correct option

Wrong answer costs 2/3 mark in GATE.

Show answer and explanation

Answer: C (official GATE 2021 final answer key)

Concept used: In a recursion tree whose subproblem fractions sum to less than 1, the work per level shrinks geometrically.

First step: Since $\frac{1}{2} + \frac{2}{5} = \frac{9}{10} < 1$ , level $i$ of the tree costs $7n(0.9)^i$ ; sum the series.

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2021 Set 1 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key