Duda Teorema Maestro

[franco-anfossi]

Hola, tengo la duda de como encontrar el c y el d para el teorema maestro, las a y el b les encuentro sentido, pero todavía no entiendo el sentido de c y d y como encontrarlo. ¿Lo otro, el teorema maestro siempre va acompañado de la n a no ser que c = 0 no?

[elneitans]

La idea es que llegues a una operación T(n) = c* n^d + a1 * T[n/b] + a2 * T[n/b] para n mayor o igual a b/(b-1), con una función techo y otra suelo. Así que, como dices más abajo, si c = 0, la n no va a aparecer en tu expresión. Para encontrar c y d, tienes que identificar tu n en la ecuación y ver el coeficiente (c) y el exponente (d) que lo acompaña. Si T(n) = n + T[n/2] + T[n/2], (con la primera [n/2] función techo y la otra suelo), tienes a1 = a2 = c = d = 1, y b = 2, por lo que a1 + a2 = b^d, y tienes que usar la ecuación del medio (T(n) = Theta (n log (n)) )

[franco-anfossi]

¡Ya gracias! Lo entiendo, pero hay veces que se me hace difícil encontrar cada parámetro, ósea lo que más he visto por ejemplo es que el b es fácil, se asocia con la cantidad de divisiones que se hace a n y los a más o menos lo mismo, depende la recursividad que haya si es la división de arriba o la de abajo, pero siempre tengo problemas en encontrar la n su exponente y la c, tienes algún consejo que pueda ser útil para encontrarlo "fácilmente". ¿Las asociaciones que dije antes están bien cierto? jaja

[seba-bug]

Ese término c*n^d se refiere a las operaciones no recursivas cuando estás en el llamado de T(n). Los llamados recursivos desde ese llamado se analizan con los piso y techo de n/b. Todo lo demás que se cuente como operaciones va en ese n^d.