# Master theorem solving

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

-
What is confusing you exactly? A proof of this fact can be found in the book Introduction to Algorithms. –  01000100 Aug 17 '12 at 12:13
It is important when asking a question to actually ask a question. Can you give us an example of what is confusing you? –  Thomas Andrews Aug 17 '12 at 12:44
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? –  John Smith Aug 17 '12 at 12:59
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? –  Thomas Andrews Aug 17 '12 at 13:16
Is this what you're looking for? Or is there something in particular that is hanging you up? –  mixedmath Aug 17 '12 at 18:30

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.