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 type of recurrence.
The recurrence relation is:

T(n) = T(n/2) + T(2n/5) + 7n

This is a divide-and-conquer recurrence with two recursive calls on subproblems of sizes n/2 and 2n/5, and a non-recursive cost that is linear in n.

---

Step 2: Apply the Akra–Bazzi theorem.
The general Akra–Bazzi form is:

T(n) = Σ T(a_in) + g(n)

Comparing terms, we identify:

a₁ = 1/2,   a₂ = 2/5,   g(n) = 7n

We now find p such that:

(1/2)^p + (2/5)^p = 1

Testing p = 1:

1/2 + 2/5 = 9/10 < 1

Since the sum is less than 1 at p = 1, the equality must hold for some value p < 1.

---

Step 3: Compare g(n) with n^p.
Here,

g(n) = Θ(n)

Since p < 1, we have:

n = Ω(n^p)

Thus, the non-recursive term dominates the contribution from the recursive calls, and the regularity condition of Akra–Bazzi is satisfied.

---

Step 4: Determine the asymptotic bound.
By the Akra–Bazzi theorem, when g(n) dominates,

T(n) = Θ(n)

---

Final Answer: (C)