Master Theorem

So for the past week, we've been doing Master Theorem. It was quite confusing at the beginning, since it is hard to believe that complicated recursive functions runtime can be analysed so easily with it. So here's the "formula" for Master Theorem:


T(n) = (n^d)             if a < b^d
          (n^d log n)     if a = b^d
          (n^(logb a))    if a > b^d

I found some exercises online and figured out that it actually works. It is a short-cut or like a cheat sheet without going through the long process of unwinding to get to the answer. This is definitely one of the most interesting theorems that I've ever encounter with.