# Explanation of a specific recurrence with respect to Master Theorem

Concerning the Master Theorem. I have found the following equation as the base of analysis:

$\quad T(n) = aT(n/b) + \Theta(n^k)$

but I also found the following:

$\quad T(n) = aT(n/b) + \Theta(n^k\cdot\log_p n)$

where the base $p$ is a real number.

Can anyone explain the second equation? I understand the proof with the first equation but can not understand the second formula.

• Your question is not clear? Where do you have "found" the formulas? What proof? Jan 20 '13 at 11:03
• They are from text-books.By proof I mean how to extract the 3 branches that specify the complexities in Master Theorem Jan 20 '13 at 11:06
• Could be related to another similar question. Jan 20 '13 at 11:28
• If you look up the wikipedia article you could see that the generic form of the second branch is $f(n) = \Theta \left(n^{\mathop{\text{log}}{}_b a} \mathop{\text{log}}{}^k n \right)$ that matches both formulas in your question. Jan 20 '13 at 13:10
• Without the algorithm being analysed we won't be able to tell you where the $\log$ comes from.
– Raphael
Jan 20 '13 at 15:27

Sometimes the master theorem is only given for recursions of the form $T(n) = aT(n/b) + \Theta(n^k)$, but the Wikipedia article includes a more general version which can handle functions of the form $T(n) = aT(n/b) + \Theta(n^k(\log n)^l)$, and even more general ones when $k \neq \log_b a$. The similar Akra-Bazzi theorem handles more general situations.