Решение повторения Т (п) = 2T (SQRT (N)) + log2n

Question

Я хотел бы решить следующее рекуррентное соотношение:

Т (п) = 2T (SQRT (п)) + log2n

К сожалению, в этом случае не может применяться ни главная теорема, ни метод arara-bazzi. Я предполагаю, что решение должно быть O (log log n), но я не уверен, как это доказать.

Большое спасибо заранее.

Answer 1

Сделаем замену:

Тогда рецидив становится:

Мы будем предполагать, что здесь log является базой 2, без потери общности.

Есть log(m) этих терминов (игнорируя вне по-одному и т.д.), так что:

• В m сроках подводить к m log(m)
• "постоянные" условия являются геометрические ряды и сумма до

(... так что мы его игнорируем)

Таким образом, общая сложность: