Стоимость алгоритма с использованием основной теоремы

Question

Здравствуйте, может кто-нибудь, пожалуйста, помогите мне с вопросом

T(n)=T(n^(1/2)) + theta (lg lg n)

Это то, что я сделал до сих пор

m = lg n
s(m)=s(m/2) + theta (lg m)

Применяя основную теорему здесь

a=1 b=2
m^log 2 (1) = m^0 =1 

сейчас застрял.

Answer 1

У тебя есть:

a = 1, b = 2
f(m) = Ө(lg(m))

Второй случай основной теоремы применяется, если:

f(m) = Ө(m^c * lg^k(m))

где:

c = log_b(a)

Проверяя это, мы имеем:

f(m) = Ө(lg(m)) = Ө(m^0 * lg(m)) 
-> c = 0
-> c = log_b(a) = log_2(1) = 0

Так что второй случай применим. Таким образом, решение этой проблемы:

T(m) = Ө(m^c * lg²(m)) = Ө(lg²(m))

Подставляя m мы возвращаемся в

T(n) = Ө(lg²(lg(n)))

Answer 2

Во-первых, T(n) = T(n^(1/2)) + theta(lg lg n) можно записать как

Т (2^(2^ к)) = Т (2^(2^(к-1))) + тета (к).

Агрегирование приведенного выше уравнения для k=1 до d дает T(2^(2^d)) = тета (d^2). Пусть n=2^(2^d), получим T(n) = theta( (lg lg n)^2).