Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
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? –  Thomas Andrews Aug 17 '12 at 13:16
1  
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

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

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.