假设我们有一个虚构的合并排序，其中合并操作的成本O(n^2)不是O(n). 然后根据主定理，我们有：
T(n) <= aT(n/b) + O(n^d)
T(n) <= 2T(n/2) + O(n^2)
由于a < b^d，我们发现：
T(n) = O(n^d)
T(n) = O(n^2)
然而，直观地说，大 O 也是有道理的，T(n) = O(n^2 logn)因为每次递归都会对数字执行二次 ( n^2) 搜索。例如，在线性搜索的情况下，归并排序是O(n logn). 有谁知道为什么没有绑定O(n^2 logn)？这可能与每次递归时搜索减半的事实有关吗？
我们可以认为正常合并排序所花费的时间如下（我们合并 2 个大小的列表n/2，我们合并 4 个大小的列表n/4，我们合并 8 个大小的列表n/8，等等）：
2(n/2) + 4(n/4) + 8(n/8) + 16(n/16) + ... + n(1)
这简化为：
n + n + n + ... + n = O(nlogn)
对于您的新合并排序，我们改为：
2(n/2)^2 + 4(n/4)^2 + 8(n/8)^2 + 16(n/16)^2 + ... + n(1)^2
这简化为：
n^2/2 + n^2/4 + n^2/8 + n^2/16 + ...
然后变成：
n^2(1/2 + 1/4 + 1/8 + 1/16 + ...) = O(n^2)
我希望这能吸引你的直觉。