Нахождение асимптотической оценки (Кормен), преобразования

[alecm]

Здравствуйте, уважаемые участники форума!
Решаю упражнение из Кормена (4.3-4), и застрял на преобразованиях. Есть ощущение, что всё должно быть просто, но так и не нашёл решение.

В общем, дело вот в чём. Дано реккурентное соотношение:
$T(n)=4T(n/2)+n^2\lg(n)$, где $\lg(n)$ - двоичный логарифм, $n$ - объём данных на входе алгоритма.
Необходимо найти верхнюю асимптотическую оценку.

Основной метод (master method) здесь не подходит, так как $n^2$ не полиномиально меньше чем $n^2\lg(n)$.

Построил дерево рекурсии, в котором мне сейчас надо найти количество уровней. Так как подзадача в дереве имеет вид $(\frac{n}{2^i})^2\lg(\frac{n}{2^i})$, где $i$ - соотвтетствующий уровень, то для нахождения количества уровней дерева рекурсии надо найти $i$, решив уравнение $(\frac{n}{2^i})^2\lg(\frac{n}{2^i})=1$.

Я, конечно, не спец в математике, но хочу пополнить свой математический багаж.
Подскажите, в какую сторону надо двигаться дальше для решения задачи?

[Sonic86]

Я незнаком с терминами из Кормена, но здесь все довольно просто: подставляете в правую часть выражение для левой части достаточно много раз - у Вас в итоге получается соотношение вида $T(n)=4^kT\left(\frac{n}{2^k}\right)+S$, где $S$ - остальная сумма с логарифмами. Поскольку при $x<1$ $T(x)=0$, то подбираем такое $k$, чтобы $T\left(\frac{n}{2^k}\right)$ стало равно нулю. А потом уже считаем сумму или ее асимптотику - что угодно.

Кстати, можете заглянуть в Конкретную математику Кнута. Там есть похожие примеры, а также методы их решения - как раз математический багаж.

[alecm]

Спасибо за ответ!
Но всё равно интересно узнать как решается это уравнение:
$(\frac{n}{2^i})^2\lg(\frac{n}{2^i})=1$.

[Sonic86]

Уравнения типа $t^2 \ln t=1$ в действительных числах в общем случае решаются численно. С помощью матана находят число корней и локализуют их (здесь вообще корень 1). А потом юзают численные или асимптотические методы.

(Оффтоп)

хотя мне неясно, зачем Вам корень этого уравнения, но сказать мне не жалко