Почему не работает аналогия асимптотики c?

Question

Недавно я столкнулся с вопросом, где была задана асимптотическая сложность c -

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. Пожалуйста, помогите мне, где я иду не так.

Answer 1

Предположение вашего аргумента неверно. T (n) = T (n / 2) + O (n) является линейным и не nlogn. Сортировка слиянием имеет рекуррентное соотношение T (n) = 2T (n / 2) + Theta (n). Фактор 2 имеет значение, потому что если вы телескопируете уравнение отношения, вы не получите экспоненциально убывающие члены, как если бы коэффициент был меньше 2.

(Примечание: ознакомьтесь с основной теоремой, которая применяется к такие отношения повторения).