Recurrencia con una función de n veces t ()

Question

El método maestro funciona bien en problemas como $ t (n)= kt (an) + cn $ , pero no maneja problemas como $$ t (n)= n ^ {\ frac {1} {3}} t (n ^ {\ frac {2} {3}}) + n ^ 2 $$ Con el número de sucursales para cada partición es una función de $ n $ .Me pregunto si hay una buena solución para este tipo de problemas, ¡no tengo idea de cómo resolver esto, se aprecia ninguna ayuda!

Answer 1

Puede usar el método más elemental en el que expande la recurrencia: \ comienzan {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} ) \\ &=CDOTS \ End {align} Esto sugiere que $ t (n)= o (n ^ 2) $ . De hecho, intentemos probar por inducción que $ t (n) \ leq cn ^ 2 $ : $$ T (n) \ leq n ^ 2 + n ^ {1/3} \ CDOT CN ^ {4/3}= N ^ 2 \ izquierda (1 + \ frac {c} {n ^ {1/3}} \ derecho), $$ que será como máximo $ cn ^ 2 $ para cualquier $ c> 1 $ y lo suficientemente grande) Clase="Math-contenedor"> $ n $ (dependiendo de $ C $ ).

De hecho, definiendo $ s (n)= t (n) - n ^ 2 $ , tenemos $$ S (n)= n ^ {5/3} + n ^ {1/3} S (n ^ {2/3}), $$ y así, el mismo argumento muestra que $ s (n)= o (n ^ {5/3}) $ y por lo $ T (n)= n ^ 2 + o (n ^ {5/3}) $ . De la misma manera, podemos obtener $ t (n)= n ^ 2 + n ^ {5/3} + o (n ^ {10/9}) $ , y así sucesivamente.