The solution of the reccurence relation \(T(n) \leq \begin{cases} \theta(1) &…
2015
The solution of the reccurence relation
\(T(n) \leq \begin{cases} \theta(1) & \text{ if } n \leq 80 \\ T\bigg(\dfrac{n}{s} \bigg)+T \bigg(\dfrac{7n}{10}+6\bigg)+O(n) & \text{ if } n> 80 \end{cases}\)
- A.
\(O(\lg n)\) - B.
\(O(n)\) - C.
\(O(n \lg n)\) - D.
None of the above
Attempted by 60 students.
Show answer & explanation
Correct answer: D
Use the Akra–Bazzi theorem to analyze the recurrence T(n) = T(n/s) + T(7n/10 + 6) + O(n). Let b1 = 1/s and b2 = 7/10, and find p satisfying b1^p + b2^p = 1.
Case 1 (s > 10/3): 1/s + 7/10 < 1, so the solution p of (1/s)^p + (7/10)^p = 1 satisfies p < 1. The nonhomogeneous term g(n)=Θ(n) dominates the homogeneous part, and Akra–Bazzi yields T(n) = Θ(n).
Case 2 (s = 10/3): 1/s + 7/10 = 1, so p = 1. In this boundary case the integral in Akra–Bazzi contributes a logarithmic factor and T(n) = Θ(n log n).
Case 3 (s < 10/3): 1/s + 7/10 > 1, so p > 1. The homogeneous part dominates and the solution is T(n) = Θ(n^p), where p is the unique exponent solving (1/s)^p + (7/10)^p = 1 (this growth is superlinear).
Conclusion: Because the asymptotic behavior depends on the unspecified parameter s, the recurrence does not have a single fixed answer among the given choices. Therefore the correct selection is the choice that reflects this ambiguity. The base case n ≤ 80 affects only constants.