Master Theorem aplicável aqui?

Question

deixe $ t (n):=begin {casos} \ frac {2+ \ log n} {1+ \ text {log} n} t (\ lFlor \ frac {n} {2} \ rfloor) + \ log ((n!) ^ {\ Log n}) & \ text {se} n> 1 \\ 1 & \ text {se} n= 1 \ end {casos} $

Eu preciso provar que $ t (n) \ in O (n²) $ , assim $ t (n ) \ leq c \ cdot n² $

Eu fiz a pergunta aqui e eu Tenho realmente grande ajuda da última vez, a coisa é depois que eu foi mostrado na última vez que $ f (n)=log (n) \ cdot \ log (n!) $ é $ \ theta (2 \ Cdot \ log (n) \ cdot n)=theta (\ log (n) \ cdot n) $ eu pensei que poderia Em seguida, use o Teorema Master

No entanto desde $ a=frac {2+ \ log n} {1+ \ log n} $ não é uma constante eu não posso usar o teorema mestre Mas eu pensei que poderia usar um limite superior para $ a $ , já que $ \ frac {2+ \ log n} {1+ log n} <2 \ quad \ forall n $ e, em seguida, use o teorema mestre para $ a= 2 $ , $ b= 2 $ . Mas tenho permissão para usar o Teorema Mestre depois de encontrar um limite superior para a não constante $ a $ ?

Quais formas formas para mostrar que $ t (n)= O (n ^ 2) $ ?

Answer 1

Sim, você pode definir $ t '(n)= 2 t' (\ frac {n} {2}) + \ theta (n \ log n) $ , observe que $ t (n) \ le t '(n) $ e use o teorema mestre na $T '$ para obter um limite superior da $ o (n \ log ^ 2 n) $ para $T $ .

Como para $ n \ GE 2 $ , $ \ frac {2+ \ log n} {1+ \log n} \ le \ frac {3} {2} $ você pode obter um limite superior melhor comparando $ t $ para $$ t '=begin {casos} \ frac {3} {2} t' '(\ frac {n} {2} {2 2}) + \ theta (n \ log n) & \ text {se $ n \ ge2 $} \\ \ theta (1) & \ text {de outro modo} \ end {cases}. $$ aplicando o teorema mestre na matemática $ T '' $ rendimentos e limite superior de $ o (n \ log n) $ para $ T $ .

Answer 2

Sim, você tem permissão para usar o teorema do mestre em limites superiores.

formalmente, basta definir S (N) como a função que tem os limites superiores (quais chamadas recursivas para ) e use o teorema do mestre em s (n).Você sabe que S (n) é um limite para t (n) (você pode provar isso em indução se você realmente quiser) e, portanto, se você conseguiu mostrar que s (n)= o (n ² ) então também t (n)= o (n ^{2 )}

Pessoalmente, nunca expliquei por que é possível usar o teorema do mestre em limites superiores também, e eu nunca vi ninguém tentar explicá-lo antes (desde que você viu da explicação, a razão é bastante simples) .

Espero conseguir ajudar: p