Recurrence complexity [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 9 years ago.

Improve this question

Find the tight asymptotic bound:

T(n) = 1 if n = 1

2T(n/4) + T(n/2) + n² if n > 1

I tried drawing a recurrence tree. First row I had n², second row I had (3/8)(n⁴), third row I had (27/1024)(n⁸).. Don't know how to continue from there. Thanks in advance.

Answer 1

I think the Master Theorem can be applied in this problem. It is much easier to understand than recurrence tree.

Write the recurrence formula in another form. Add T(n/2) to both the left and right side.

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

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

Define G(n) = T(n) + T(n/2), then

G(1) = Θ(1)

G(n) = 2G(n/2) + n², if n > 1

Apply the Master Theorem to the above new recurrence formula

G(n) = Θ(n²)

that is

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

for n > 1

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

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

= T(n/4) + Θ(n2/4) + n2

= T(n/4) + Θ(n2)

Apply the Master Theorem to the above new recurrence formula

T(n) = Θ(n2)