Каковы асимптотические верхние и нижние оценки для T (n) = 2T (n / 2) + n lg lg n?

Question

Рекуррентное соотношение

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

(где lg - логарифм к основанию 2) можно решить с помощью основной теоремы , но я не очень уверен в ответе.Я нашел свой ответ, но не упоминаю его здесь, чтобы предотвратить информационные каскады.Пожалуйста, помогите мне найти большие O и Ω для выше.

Answer 1

Ни один из 3 случаев в основной теореме не применим для

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

(При произвольном основании это не имеет значения)

Случай 1: f (n) = nlog (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).