Теория алгоритмов. Рекурсия, время работы.

[Kornelij]

Время работы алгоритма зависит от числа $n$ следующим образом: $t(n)=t\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + t\left(\left\lceil \frac{n}{2} \right\rceil \right) + cn$,
где $c>0$, $t(0)=t(1)=0$.
Вопрос: как доказать без основной теоремы о рекуррентных соотношениях, что $t\in O(n\log(n))$?

[kp9r4d]

Ну если $n=2^k$ то совсем просто, наверное?

[Kornelij]

kp9r4d в сообщении #1222818 писал(а):

Ну если $n=2^k$ то совсем просто, наверное?

Да, это хорошая идея. Спасибо!