1 Master公式推导
对于一个递归问题，其花费的时间应为：调用子问题的时间+除子问题外的操作所花费的时间。假设其数据量规模为n，每一次的递归行为中，调用子递归行为的次数为，数据规模为上一次的
，那么其常数操作次数记为：
其中为本次递归行为中，除去调用子递归行为外的常数操作次数的最高阶（刨除常数项），记为：
如此便得到了递归问题的递推公式。我们进一步往下推导：
刨除常数项，取最高阶，得到大表示法的时间复杂度：
诸如，表达的是
的渐进上界为
，即
的阶不高于
。
2 例子
下面举几个例子：
二分查找：，
，
。
归并排序：，
，
。
并非所有的递归问题都能用Master公式求解，非平均划分子式的递归式以及递归式中无法找到渐进上界，都无法应用Master公式。但是对于一般的问题（面试可能遇到的）也足够应对了。
