0
$\begingroup$

I'm starting to study the master theorem, why does something like

$$T(n) = aT(n/b)+f(n)$$

solves to

$$f(n)^{\log_ba}$$ ?

I'm a bit confused on the resolution

  • 1
    What is confusing you exactly? A proof of this fact can be found in the book Introduction to Algorithms.2012-08-17
  • 0
    It is important when asking a question to actually ask a question. Can you give us an example of what is confusing you?2012-08-17
  • 0
    I don't know where the second formula came from, @DanielPietrobon is that explained where the second formula come from in the book you cited?2012-08-17
  • 1
    Again, "where the second formula came from" is not a clear question. Are you looking for the history of the formula, a proof of why the formula works, or some other question?2012-08-17
  • 0
    How that formula is obtained, just that2012-08-17
  • 1
    Is [this](http://lmgtfy.com/?q=proof+of+master+theorem) what you're looking for? Or is there something in particular that is hanging you up?2012-08-17
  • 0
    Here is Wikipedia's version of the [Master Theorem](http://en.wikipedia.org/wiki/Master_theorem#Generic_form).2012-08-17
  • 0
    I think it is obvious he was looking for the derivation of the formula, the (algebraic) steps to go from on to the other... really, was it so difficult to pick up the intended meaning of the question?2012-12-28

2 Answers 2

2

The right way to think about this is that we reduce the original problem, of size $n$, to $a$ separate problems of size $n/b$, and we do this recursively. At stage $i$, there are $a^i$ problems of size $n b^{-i}$. For each such problem, we need to do something which costs $f(x)$ on a problem of size $x$. Hence, the total cost at level $i$ is $a^i f(n b^{-i})$.

This recursion has $\log_b n$ levels, so the total work consumed at all levels is $$ \sum_{i=0}^{\log_b n} a^i f(n b^{-i}) $$

Depending on the growth of $f$, this is basically a geometric series.

0

For an in depth explanation and proof of the "Master Theorem" or "Master Method" of finding asymptotic solutions to recurrences, see MIT OCW's Introduction to Algorithms, Lecture 2.