Оценить рекурсивную последовательность

[ShMaxG]

$$ T\left( n \right) = \sqrt n \cdot T\left( {\sqrt n } \right) + n $$

Прихожу к сумме

$$ n + n^{1/2} + n^{1/4} + ... $$

, которую тоже не могу оценить...

[Xaositect]

$T(n) = \sqrt{n}T(\sqrt{n}) + n$
$\frac{T(n)}{n} = \frac{T(\sqrt{n})}{\sqrt{n}} + 1$
$L(n) = L(\sqrt{n}) + 1$
$L(2^2k) = L(2^k) + 1$
$L(2) = c \Rightarrow L(2^{2^t}) = t+c$
То есть надо попробовать что-нибудь типа $L(n) = O(\log\log n)$

[ewert]

а я вот не вижу тут последовательности. Что такое $T(\sqrt n)$, коль уж скоро это последовательность?...

[ShMaxG]

А, во.

$$ L\left( n \right) = L\left( {\sqrt n } \right) + 1 $$

Дерево рекурсии этой штуки дает

$$ {\lg \lg n} $$

единичек.
Значит

$$ T\left( n \right) = nL\left( n \right) = n\lg \lg n $$

Спасибо!

Добавлено спустя 1 минуту 47 секунд:

ewert
Да, надо было писать "Найти ассимптотическую оценку решения рекуррентного соотношения"