Quali sono i limiti superiori e inferiori asintotica per T (n) = 2T (n / 2) + n lg lg n?

Question

La relazione ricorrente

T ( n ) = 2T ( n / 2) + n lg lg n

(dove LG è logaritmo in base 2) può essere risolto utilizzando il teorema ma non sono molto sicuro della risposta. Ho trovato la mia risposta, ma non sto menzionare qui al fine di prevenire cascate di informazione. Ti prego, aiutami a trovare il grande O e O per sopra.

Answer 1

Nessuno dei 3 casi nel teorema si applicano per

T(n)=2 T(n/2) + n log(log n)

(Con base arbitraria, ma non importa)

Caso 1: f (n) = n log (log n) è 'grande' di n ^{log2 2} = n ¹

Caso 2: f (n) non si adatta n log ^k (n)

Caso 3: f (n) è più piccolo di n ^{1 + e}

U(n)=2 U(n/2) + n log n
L(n)=2 L(n/2) + n

E 'possibile dimostrare che: U(n) >= T(n) e L(n) <= T(n). Così U dà un limite superiore, e L un limite inferiore per T.

Applicando il teorema master per U (n), dà

Caso 2: f (n) = n log n = T (n ¹ log ¹ n) così U (n) = T (n log ² n)

Applicando il teorema master per L (n), dà

Caso 2: f (n) = n = T (n ¹ log ⁰ n) quindi L (n) = T (n log n)

A causa L(n)<=T(n)<=U(n) segue che T (n) = O (n log ² n) e T (n) = O (n log n)

Si noti inoltre che O (log ₂ n) = O ((log n) / log 2) = O ((log n) * c) = O (log n).