Question 40

The given recurrence is $T(n) = T(n/2) + T(2n/5) + 7n$ for $n > 0$, with base case $T(0) = 1$.

Let us examine the total non-recursive work performed at each level of the recursion tree:

• Level 0 (root): $7n$
• Level 1: $7(n/2) + 7(2n/5) = 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$

Because the branch sum factor $\frac{1}{2} + \frac{2}{5} = \frac{9}{10} < 1$, the work per level forms a strictly decreasing geometric series dominated by the root level:

Alternatively, applying the Akra-Bazzi theorem, $p$ is the solution to $(1/2)^p + (2/5)^p = 1$. Since $(1/2)^1 + (2/5)^1 = 9/10 < 1$, $p < 1$. Because $g(n) = 7n = \Theta(n^1)$ grows strictly faster than $n^p$, $T(n) = \Theta(n)$.

Hence, $T(n) = \Theta(n)$, matching option C.