self doubt apply

Question

can masters theorem be used when base condition is given in a recurrence ?

can we directly apply masters theorem to any recurrence ?

Answer 1

It is only applicable when Base condition is True for given Recurrence Relation.

Master theorem can apply to any recurrence relation if it has following format,

$T \left ( n \right ) = a T \left ( \frac{n}{b} \right ) + n^{k}log^{p}n$

where, $a \geqslant 1, b > 1, k \geqslant 0$

and P is read number.

Comments

BY BASE CONDITION WHAT I MEANT WAS IN THE RECURRENCE BROTHER NOT THOSE ONES

---

Yes, It can be apply.

---

Base conditions only represents How recursive function ends and How many calls it needs !! So, Yes Master theorem can be apply to any recurrence relation.