* "О большое"

[Kornelij]

$f(n)=nlog(n)$, $g(1)=0$, $g(n)=2g([n/2])+nlog(n), n>1.$. Как доказать, что $g\in O(f)$?
Я понимаю, что нужно оценить одну функцию второй, домноженной на константу, но сбивает то, что функция $g(n)$ задана рекуррентно, а ее общий вид найти никак не получается. Видимо можно как-то обойтись без явного вида, но как?

[DeBill]

Kornelij в сообщении #1316930 писал(а):

а ее общий вид найти никак не получается. Видимо можно как-то обойтись без явного вида, но как?

Видимо, можно. Однако, доказать Ваше утверждение совсем непросто. Проще доказать, что оно неверно (и тоже можно обойтись без явного вида). Примерно, так: будем доказывать по индукции, что $g(n) >\varepsilon \cdot n\cdot (\log(n))^2 $, логарифм пусть двоичный, а $\varepsilon < \frac{1}{2}$ - достаточно малое, чтоб база имелась. Получится...

(Оффтоп)

Похоже, Вы пытаетесь оценить сложность некоего алгоритма, основанного на половинном делении - и неудачно. Сравните: для алгоритма "упорядочить массив", добавок в рек. формуле - существенно меньше итогового $f$

-- 03.06.2018, 01:09 --

Кстати, полученная оценка снизу показывает , какой должна быть правильная оценка для $g$ сверху, и доказывать ее можно так же (только считая "эпсилон" достаточно большим....)

[Kornelij]

DeBill, я дико извиняюсь, но в условии вместо $f(n)=nlog(n)$ должно быть $f(n)=nlog^2(n)$. И все равно не понимаю, как оценить $g(n)$ по индукции. Ну базу покажем легко, а дальше-то как? Если шаг индукции делать при четном $n$, то все тоже несложно, а вот при нечетном совсем непонятно.

[adfg]

Kornelij
Возьмите в качестве $n$ степень двойки, и получите в этом случае $g(n)$, там ответ можно выписать в явном виде. Произвольное $n$ оцените сверху/снизу ближайшими степенями двойки и воспользуйтесь свойством монотонности

[Kornelij]

adfg, спасибо!

[DeBill]

Kornelij
Или :
Индукцию иногда удобно вести так:
Доказывать, что утверждение У(k) верно для всех k, не превышающих n...И вот тут уже шагать по n...