主定理一般形式是T(n) = a T(n / b) + f(n)， a >= 1, b > 1。递归项可以理解为一个高度为 logn 的 a 叉树， 这样 total operation就是 (a ^ logn) - 1， 右边的f(n)假设为 n 那么我们对比一下这两项就会发现 T(n)的复杂度主要取决于 loga 与 c 的大小。所以我们才会有接下来的三种case。也需要注意什么时候不可以使用主定理。
Case 1: c < loga , O(n) = n ^ loga , 意味着我们可以忽略 f(n)
Case 2: c = loga, O(n) = nlogn , k >= 0
Case 3: c > loga, O(n) = n
Reference:
https://en.wikipedia.org/wiki/Master_theorem