GATE CS 2021 Set 1 Q30 — Asymptotic Worst Case Time and Space Complexity

We can solve this recurrence relation using the recursion tree method.

Let us analyze the cost at each level of the recursion tree:

• Level 0: $7n$
• Level 1: $7\left(\frac{n}{2}\right) + 7\left(\frac{2n}{5}\right) = 7n\left(\frac{1}{2} + \frac{2}{5}\right) = 7n\left(\frac{9}{10}\right)$
• Level 2: $7n\left(\frac{9}{10}\right)^2$
• Level $k$: $7n\left(\frac{9}{10}\right)^k$

The total cost $T(n)$ is the sum of the costs at all levels. Since the work at each level decreases geometrically, we can upper-bound the total cost by an infinite geometric series:

Since the root level alone contributes $7n$, we also have $T(n) \ge 7n$. Therefore, we get:

Thus, the correct option is C.