2001-gre-vs-practice.pdf/Q58

Ссылки сюда (1) →

Вопрос: Q58-e5724f

Какую из следующих функций можно считать наилучшей верхней границей для значения ,

где — это решение рекуррентного соотношения

с начальным условием ?

Ответы

Правильный ответ:

Объяснение

Исходники — вопрос 58 на 41 странице книги «2001-gre-vs-practice.pdf»

У нас есть два варианта рекурсии: и

Рассмотрим, что происходит на каждом шаге рекурсии. Каждый раз мы делим пополам и добавляем . Это аналогично тому, как в процессе рекурсии мы получаем сумму логарифмов на каждом шаге: Каждый шаг добавляет , и количество шагов примерно равно , так как делится пополам на каждом шаге.