madeeasy

Question

how to apply masters theorem in this type of cases!????!

Comments

You can't - you'll have to do it either by induction or substitution.

---

for master theorem it must be of form T(n)=aT(n/b)+0(n^klog^pn) a>=1 b>1 k>=0 p is real number.

for your question use tree method

Answer 1

You can't use master theorem everywhere. That's the limitation of it.

You have to do it by natural methods such as back substitution, and recurrence tree method.

Try forming some kind of series and mapping a few steps. You will identify some pattern then.