Récurrence avec une fonction de n fois t ()

Question

La méthode principale fonctionne bien sur des problèmes tels que $ t (n)= kt (an) + cn $ , mais cela ne traite pas de problèmes comme $$ t (n)= n ^ {\ frac {1} {3}} t (n ^ {\ frac {2} {3}}) + n ^ 2 $$ Avec le nombre de branches pour chaque partition est une fonction de $ n $ .Je me demande s'il y a une bonne solution à ce genre de problèmes, je n'ai aucune idée de la façon de résoudre ce problème, aucune aide est appréciée!

Answer 1

Vous pouvez utiliser la méthode la plus élémentaire dans laquelle vous élargissez la récurrence: \ commence {align} 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} ) \\ &=CDOT \ fin {align} Cela suggère que $ t (n)= O (n ^ 2) $ . En effet, essayons de prouver par induction que $ t (n) \ leq cn ^ 2 $ : $$ T (n) \ leq n ^ 2 + n ^ {1/3} \ cdot cn ^ {4/3}= n ^ 2 \ gauche (1 + \ frac {c} {n ^ {1/3}} \ droite), $$ qui sera au plus $ CN ^ 2 $ pour tout $ C> 1 $ et assez grand Classe="Math-Conteneur"> N $ N $ (Selon $ C $ ).

En effet, définissant S (n) $= t (n) - n ^ 2 $ , nous avons $$ S (n)= n ^ {5/3} + n ^ {1/3} s (n ^ {2/3}), $$ et donc le même argument montre que s (n) $= O (n ^ {5/3}) $ et donc $ T (n)= n ^ 2 + o (n ^ {5/3}) $ . De la même manière, nous pouvons obtenir $ t (n)= n ^ 2 + n ^ {5/3} + o (n ^ {10/9}) $ , et ainsi de suite.