Recorrência com uma função de n vezes t ()

Question

O método mestre funciona bem em problemas como $ t (n)= kt (A) + cn $ , mas não lida com problemas como $$ t (n)= n ^ {\ frac {1} {3}} t (n ^ {\ frac {2} {3}}) + n ^ 2 $$ Com o número de filiais para cada partição é uma função da $ n $ .Eu me pergunto se há uma boa solução para esse tipo de problema, eu não tenho ideia de como resolver isso, qualquer ajuda é apreciada!

Answer 1

Você pode usar o método mais elementar no qual você expande a recorrência: \ begin {alinhar} T (n) &= n ^ 2 + n ^ {1/3} t (n ^ {2/3}) \\ &= n ^ 2 + n ^ {5/3} + n ^ {5/9} T (n ^ {4/9}) \\ &= n ^ 2 + n ^ {5/3} + n ^ {10/9} + n ^ {19/27} t (n ^ {8/27} ) \\ &=cdots \ final {alinhar} Isso sugere que $ t (n)= O (n ^ 2) $ . De fato, vamos tentar provar por indução que $ t (n) \ leq cn ^ 2 $ : $$ T (n) \ leq n ^ 2 + n ^ {1/3} \ cdot cn ^ {4/3}= n ^ 2 \ left (1 + \ frac {c} {n ^ {1/3}} \ direito), $$ que será no máximo $ cn ^ 2 $ para qualquer $ c> 1 $ e grande o suficiente $ n $ (dependendo da $ c $ ).

De fato, definindo $ s (n)= t (n) - n ^ 2 $ , nós temos $$ S (n)= n ^ {5/3} + n ^ {1/3} s (n ^ {2/3}), $$ E assim o mesmo argumento mostra que $ s (n)= o (n ^ {5/3}) $ e assim $ T (n)= n ^ 2 + O (n ^ {5/3}) $ . Da mesma forma, podemos obter $ t (n)= n ^ 2 + n ^ {5/3} + O (n ^ {10/9}) $ e assim por diante.