Master Theorem

Master Theorem(主定理)

主定理用于在divide&conquer问题中求时间复杂度，以前总是记不住，今天总结了一下，方便记忆。

Example: merge sort: T(n) = 2*T(n/2)+O(n)

a = 2, b =2, n^logba == n, 所以符合2.1, 所以结果是O(nlogn)