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?

We can solve the recurrence using the Recursion Tree Method or the Akra-Bazzi Theorem.

### Method 1: Recursion Tree Analysis

At each level of the recursion tree, we sum the non-recursive work performed:

• 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$

Summing the work across all levels:

Since this is an infinite geometric series with common ratio $r = \frac{9}{10} < 1$:

### Method 2: Akra-Bazzi Theorem

The recurrence is of the form $T(n) = \sum_{i=1}^k a_i T(b_i n) + g(n)$, where $a_1=1, b_1=1/2$, $a_2=1, b_2=2/5$, and $g(n) = 7n$.

Find $p$ such that:

Evaluating at $p = 1$:

Since the sum decreases as $p$ increases, we must have $p < 1$.

The solution is given by:

Since $p < 1$, the integral evaluates to:

Therefore:

Hence, the correct option is (C).