为什么渐进复杂性类比不起作用？

Question

最近我遇到一个问渐近复杂性的问题-

T(n, n) where
T(x, c) = Θ(x) for c ≤ 2,
T(c, y) = Θ(y) for c ≤ 2, and
T(x, y) = Θ(x + y) + T(x/2, y/2).

提议的解决方案是

We may then begin to replace T(x/2, y/2) with the recursive formula containing it:
x + y x + y x + y
T(x, y) = c (x + y) + c(x+y)/4 + c(x+y)/8 ...
This geometric sequence is bounded from above by 2c(x + y), and is obviously
bounded from below by c(x + y). Therefore, T(x, y) is Θ(x + y), and so T(n, n)
is Θ(n).

现在我争论的是对于合并排序类型算法，其中>

 T(n) = T(n/2) + O(n) 
由此产生的时间复杂度为nlog（n）我无法理解这两个问题之间的区别，按照我的类比，第一个问题也应该是nlogn。请帮我哪里错了。

最近，我遇到一个询问渐近复杂度的问题-T（n，n），其中对于c≤2，T（x，c）=Θ（x），对于c≤T，（T，c，y）=Θ（y） c≤2，并且T（x，y）=Θ（x + y）+ T（x / 2，y / 2）。以及拟议中的...

Answer 1

您的论点有缺陷。 T（n）= T（n / 2）+ O（n）是线性的，不是nlogn。合并排序的递归关系为T（n）= 2T（n / 2）+ Theta（n）。因子2之所以有所不同，是因为如果您伸缩关系方程，则当因子小于2时，不会像您一样得到指数递减的项。]