0
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Your question is not clear? Where do you have "found" the formulas? What proof? $\endgroup$ – A.Schulz Jan 20 '13 at 11:03
  • $\begingroup$ They are from text-books.By proof I mean how to extract the 3 branches that specify the complexities in Master Theorem $\endgroup$ – Cratylus Jan 20 '13 at 11:06
  • $\begingroup$ Could be related to another similar question. $\endgroup$ – Dmitri Chubarov Jan 20 '13 at 11:28
  • 2
    $\begingroup$ 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. $\endgroup$ – Dmitri Chubarov Jan 20 '13 at 13:10
  • 1
    $\begingroup$ Without the algorithm being analysed we won't be able to tell you where the $\log$ comes from. $\endgroup$ – Raphael♦ Jan 20 '13 at 15:27
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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