# 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? –  A.Schulz Jan 20 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 –  Cratylus Jan 20 at 11:06
Could be related to another similar question. –  Dmitri Chubarov Jan 20 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. –  Dmitri Chubarov Jan 20 at 13:10
Without the algorithm being analysed we won't be able to tell you where the $\log$ comes from. –  Raphael Jan 20 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.