What are the asymptotic upper and lower bounds for T (n) = 2T (n / 2) + n lg lg n?

Question

Recurrence ratio

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

(where lg is the logarithm to the base 2) can be solved using the main theorem , but I'm not very sure about the answer. I found my answer, but I do not mention it here to prevent cascades of information. Please help me find large O and Ω for above.

Answer 1

None of the three cases in the main theorem apply to

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

(With an arbitrary base, this does not really matter)

1: f (n) = n log (log n) "", n ^{log2 2}= n ¹

2: f (n) n log ^k (n)

3: f (n) n ^{1 + e}

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

, : U(n) >= T(n) L(n) <= T(n). , U , L - T.

U (n),

2: f (n) = n log n = Θ (n ¹ log ¹ n), , U (n) = Θ (n log ² n)

L (n),

2: f (n) = n = Θ (n ¹ log ⁰ n), , L (n) = Θ (n log n)

L(n)<=T(n)<=U(n) , T (n) = O (n log ² n) T (n) = Ω (n log n)

, O (log ₂ n) = O ((log n)/log 2) = O ((log n) * c) = O (log n).