Question

Please tell how to apply Akra Bazii in the following recurrence :

T(n)=T(n/2)+ T(n/4) +n²

Comments

yes, it will be O(n²)..

---

@nitish verify this

T(n) = T(n/2) + T(n/4) + n²

T(n) <= T(n/2) + T(n/2) + n²

T(n) <= 2T(n/2) + n²

And then applied Master's theorem,

a = 2, b = 2, k = 2 and p = 0

Since a < b^k and p>=0, T(n) = O(n^k(logn)^p) = O(n²)

---

i have done using tree method..

try to apply tree method for these qsns, though here it doesn't affect answer, sometime it might give incorrect answer..