Решите рецидив с помощью теоремы мастера

Question

Это рекурсивная формула, для которой я пытаюсь найти асимптотическую закрытую форму Мастер теорема: $$ t (n) = 9t (n/27)+(n cdot lg (n))^{1/2} $$

Я начал с $ a = 9, b = 27 $ и $ f (n) = (n cdot lg n)^{1/2} $ для использования мастер -теоремы по $ n^{ log_b (a)} $, и если так, так как $ n^{ log_ {27} (9)} = n^{2/3} $, но я не понимаю, как играть с $ (n cdot lg n)^{1 /2} $.

Я думаю, что $ (n cdot lg n)^{1/2} $ больше, чем $ n^{2/3} $, но я уверен, что пропустил здесь что -то.

Я думаю, что это соответствует третьему случаю теоремы Мастера.

Answer 1

$ f (n) = (n cdot lg n)^{1/2} $ и $ n^{ log_b a} = n^{2/3} $, таким образом $ f (n) = O (n ^{ log_b a}) $ и даже $ f (n) = o (n^{ log_b a - epsilon}) $ для $ epsilon <1/6 $.

Почему? Потому что $$ lim_ {n to infty} frac {f (n)} {n^{ log_b a - epsilon}} = lim_ {n to infty} frac {n^{1/ 2} lg^{1/2} n} {n^{2/3- epsilon}} = lim_ {n to infty} frac { lg^{1/2} n} {n^ {1/6- epsilon}} = 0 Quad text {for} epsilon <1/6 $$

Таким образом, случай 1 теоремы Мастер должен применяться, и $ t (n) = theta (n^{2/3}) $.