Рекуррентное соотношение

[capt]

DeBill
1) Не совсем понятно, что значит "достаточно малым". Чему все таки должно быть равно $c$ или это не обязательно искать?
2) можно ли в качестве базы индукции взять $n = N$?

[DeBill]

capt в сообщении #1409286 писал(а):

1) Не совсем понятно, что значит "достаточно малым". Чему все таки должно быть равно $c$ или это не обязательно искать?

Ну, это - смотря что мы хотим доказать.... Если хочется установить неравенство $T(n)> cn \ln n $ для всех $n$, то нужную константу придется подбирать довольно нудно...
Но если надо всего лишь показать, что $T(n)= \Omega (n \ln n)$ , то такие рассужденияя (показывающие, что для какой-то (неважно, какой) константы все получится ) вполне годятся...
2. Нет. Фишка в том, что для шага индукции у нас используется предположение о выполнении неравенства для $\frac{n}{2}$, и шаг удается сделать только при $n>N$. Так что, чтобы шагать можно было, надо - большую базу....
Ну, вот, например, пусть $N=100$. Чтобы получить неравенство для $n=101$, нужно его уже иметь для $n=50$ - в базу его. Чтоб иметь при $n=180$, например, надо его уже иметь при $n=90$.... Так что здесь - без шагов индукции, на базе - придется отдельно проверять неравенство при всех $n$ от 50 до 100. (И при этом мы - индукцией - установим неравенство для всех $n$, больших 50. А если хочется таки заиметь неравенство для всех $n$ то и первую полсотню придется проверить).