alt text

задан 5 Июл '15 18:33

10|600 символов нужно символов осталось
1

Из уравнения следует, что $%T(1)=1$%. Индукцией по $%k$% легко проверяется, что $%T(2^k)=2^k(k+1)$%. Далее, функция $%T(n)$% монотонно не убывает, что также доказывается при помощи индукции.

Теперь для произвольного $%n$% выбираем такое $%k$%, для которого $%2^k\le n < 2^{k+1}$%. Тогда $%T(n)\ge T(2^k)=2^k(k+1) > \frac{n}2\,\log_2n=\Omega(n\log n)$%.

ссылка

отвечен 5 Июл '15 20:41

Последнее неравенство $%2^k(k+1) > \frac n2 \cdot \lg n$% получается из того что $%k+1 > \lg n$% и $%2^k > \frac n2$%?

(7 Июл '15 19:46) Leva319

@Leva319: да, именно так!

(7 Июл '15 20:53) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×65
×22

задан
5 Июл '15 18:33

показан
612 раз

обновлен
7 Июл '15 20:53

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru