Решение рекуррентного соотношения T(n) = √n T(√n) + n

Это не может быть решено с помощью основной теоремы. Однако это можно решить с помощью метода дерева рекурсии, чтобы разрешить O (n log log n).

Интуиция, стоящая за этим, заключается в том, чтобы заметить, что на каждом уровне дерева вы выполняете n работы. Верхний уровень не работает явно. Каждая из √n подзадач выполняет √n работ, что в сумме составляет n работ и т. д. Таким образом, теперь вопрос заключается в том, насколько глубоко дерево рекурсии. Ну, это количество раз, которое вы можете извлечь квадратный корень из n, прежде чем n станет достаточно маленьким (скажем, меньше 2). Если мы напишем

n = 2^{lg n}

тогда при каждом рекурсивном вызове n будет извлекаться квадратный корень. Это эквивалентно уменьшению указанного выше показателя степени вдвое, поэтому после k итераций мы имеем это

n^1/(2k) = 2^{lg n/(2k)}

Мы хотим остановиться, когда это меньше 2, давая

2^{lg n/(2k)} = 2

lg n/(2^k) = 1

lgn = 2^k

lg lg n = k

Таким образом, после lg lg n итераций извлечения квадратного корня рекурсия останавливается. И, поскольку на каждом уровне рекурсия работает O(n), общее время выполнения равно O(n lg lg n).

В более общем смысле, точно так же, как любой алгоритм, который многократно сокращает размер входных данных вдвое, должен заставить вас думать о log n, любой алгоритм, который многократно сокращает размер своих входных данных, извлекая квадратный корень, должен заставить вас думать о log log n. Деревья ван Эмде Боаса используют это повторение, например.

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