Решение рекурсии с показательным правилом, где основная теорема не применяется

Question

Я пытаюсь решить следующее повторение:

$T(n) = 3T(n^{\frac{2}{3}}) + \log n$

, но не уверен, как это сделать, так как теорема Мастера не применяется. Я попытался нарисовать дерево рекурсии следующим образом:

, но я не уверен, откуда go, например, пытаясь выяснить высоту дерева или количество узлов в последнем слое. Любое руководство о том, как найти общую большую тэту повторения, будет оценено.

Answer 1

При расширении формулы у нас будет:

T(n) = 3 log(n^{2/3}) +‌ 3^2 log(n^((2/3)^2)) + ... + 3^k log(n^((2/3)^k)) + log(n)

В приведенном выше уравнении k - это высота дерева. Если мы предположим, n = 2 ^ ((3/2)^k), наконец, у нас будет 2 в n^((2/3)^k). Следовательно, k = log_{3/2)(log(n)). Также мы знаем, что log(n^a) = a log(n):

T(n) = 2 log(n) + 2^2 log(n) + ... + 2^k log(n) + log(n) = 
         log(n) (1 + 2 + 2^2 + ... + 2^k) =
         (2^(k+1) - 1) log(n)

Следовательно, как 2^k = O(log^2(n)), T(n) = O(log^2(n) * log(n)) = \O(log^3(n)).