Question

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? 
 

• A. \(T(n) = \Theta(n^{5/2})\)
• B. \(T(n) = \Theta(n \log n)\)
• C. \(T(n) = \Theta(n)\)
• D. \(T(n) = \Theta((\log n)^{5/2})\)

Hint:

For recurrences with unequal subproblem sizes, the Akra–Bazzi theorem is often more powerful than the Master Theorem.

Answer 1

The Correct Option is C

Step 1: Identify the form of the recurrence.
The given recurrence is: \[ T(n) = T(n/2) + T(2n/5) + 7n \] This is a divide-and-conquer recurrence with two subproblems of sizes \(n/2\) and \(2n/5\), along with a linear non-recursive cost \(7n\).

Step 2: Apply the Akra–Bazzi theorem.
We compare the recurrence with the Akra–Bazzi form: \[ T(n) = \sum_{i=1}^{k} T(a_i n) + g(n) \] Here, \[ a_1 = \frac{1}{2}, a_2 = \frac{2}{5}, g(n) = 7n \] We find \(p\) such that: \[ \left(\frac{1}{2}\right)^p + \left(\frac{2}{5}\right)^p = 1 \] Testing \(p = 1\): \[ \frac{1}{2} + \frac{2}{5} = \frac{5 + 4}{10} = \frac{9}{10} < 1 \] Testing \(p < 1\) increases the sum, so the equality holds for some \(p < 1\). Hence, \[ p < 1 \]

Step 3: Compare \(g(n)\) with \(n^p\).
Since \(g(n) = \Theta(n)\) and \(p < 1\), we have: \[ g(n) = \Omega(n^p) \] and the regularity condition is satisfied.

Step 4: Conclude the asymptotic bound.
By the Akra–Bazzi theorem, when \(g(n)\) dominates the recursive terms, \[ T(n) = \Theta(n) \]

Final Answer: (C)