How to memorize Master Theorem?

Question

I know the maths behind, I know if I do the algebra I can get the result of the 3 cases. I also have an intuition of the 3 cases: Quora

However, I just cannot memorize this "simple" 3 cases whenever I need to apply them in real life problems.

I don't know if it is a shame that a CS graduate has to Google this theorem, which I learnt at the first year in University, just because I cannot memorize it. (Or is it actually no need to memorize it, please tell me, I will close the question at once)

---

So assuming this basic theorem is important and I have to memorize it just like how we memorize F = ma in physics field, is there any way to aid memorizing these 3 cases in long term speaking?

A way may means visualization, better intuition with clear reasoning behind, or even just die hard memorizing it, I just want to know how other CS people memorize this theorem.

Answer 1

I have a confession for you. I often can't remember the Master theorem, either. Don't worry about it. It's not a big deal.

Here's how I deal with it. In many situations, you can look it up each time you need it; and if so, no big deal.

Occasionally, you might not be able to look it up. So, I taught myself how to derive the Master theorem. That might sound intimidating, but it's not as hard as it sounds. Personally, I find memorization hard, but if I can figure out how to re-derive the formula myself whenever I need it, I know I'm in good shape.

So, my advice to you is: learn how to re-derive the Master theorem on your own, whenever you need it. Here's one way you could do that:

• First, learn the recursion tree method. Learn how to build the tree, how to count the number of leaves, and how to count the amount of "extra work" at each level, and how to sum them (by summing a series, e.g., a geometric series).

• Next, open up a textbook read a standard proof of the Master theorem. Work through each step and check that you understand what's happening.

• Now, close your textbook and put away all your resources. Put a blank piece of paper in front of you... and derive the Master theorem yourself. How do you do that? Well, you use the recursion tree method. Try working through it by yourself and try to solve the recurrence entirely on your own. If you get stuck, as a last resort you can open the textbook back up and see how to proceed from there... but then the next day, you should try this exercise again.

If you understand the recursion tree method well, you should be able to get to the point where you can derive the Master theorem yourself, from scratch, using just a blank piece of paper and nothing more.

Answer 2

The key to memorizing the master theorem is to simplify it. There's an approximation to reality that is correct in 99% of the cases. A good (but not technically correct) summary of the Master Theorem is as follows:

If $T(n)=aT(n/b) + f(n)$ then compare $n^{log_b a}$ with $f(n)$

• If $f(n) < n^{log_b a}$, then $T(n)=n^{log_b a}$

• If they are equal, then $T(n)=f(n)\log n$

• If $f(n) > n^{log_b a}$, then $T(n)=f(n)$

Basically, you compare $n^{log_b a}$ with $f(n)$ and the larger of the two is your running time; however if they are equal (for some strange definition of equal) then you get an extra $log$-factor in the running time. This sentence is all you really need to know.

Caveats

The most important one is in the meaning of "equal". For the purpose of the master theorem $f(n)$ is equal to $n^{log_b a}$ if the difference between them is less than polynomial. So, for instance, if $f(n)=n^{log_b a}\log n$ or $f(n)=n^{log_b a}\log^3 n \log \log n$ this would still count as "equal". The difference needs to be at least a factor $n^\epsilon$ for some $\epsilon>0$.

Another caveat is that for the third case ($f(n)$ exceeds $n^{log_b a}$ you also need a condition that $f(n)$ does not grow "too quickly". This is rather pathological and not likely to be an issue in practice, but something you should be aware of. The formal condition is that $af(n/b)$ should be less than $f(n)$ (for sufficiently large $n$, and where "less" is interpreted as "there is a $k<1$ such that $af(n/b)\leq kf(n)$).

Answer 3

It is better if you go through its proof and understand it.But if you want to remember then you should make note of these few points:

It is applicable to recurrences of following form:

Then calculate $$ x=\ Log_ba $$

1. if c < x then $$ T(n)=\theta(n^x) $$

2. if c = x then $$ T(n)=\theta(n^cLog n) $$

3. if c > x then $$ T(n)=\theta(n^c) $$

Also go through Master's Theorem eligibility for situations having limitations with this theorem.

I hope it makes sense to you.....