How to memorize Master Theorem?

Problem Detail: 

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.

Asked By : shole

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/60157