snippetMinor
How to memorize Master Theorem?
Viewed 0 times
memorizemastertheoremhow
Problem
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
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.
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.
Solution
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)
-
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)$).
If $T(n)=aT(n/b) + f(n)$ then compare $n^{log_b a}$ with $f(n)$
-
If $f(n)
-
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)$).
Context
StackExchange Computer Science Q#60157, answer score: 9
Revisions (0)
No revisions yet.