Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Your question is not clear? Where do you have "found" the formulas? What proof? – A.Schulz 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 – Cratylus Jan 20 '13 at 11:06
Could be related to another similar question. – Dmitri Chubarov 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. – Dmitri Chubarov 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.