T (n) = t (n - sqrt (n))

Question

¿Alguien sabe cómo resolver esta recurrencia?

El teorema maestro no funciona aquí.

Answer 1

Parece obvio en o (1) ya que

T(n) = T(n - sqrt(n)) = T(m) with 0 < m < n

Por inducción, obtienes t (n) = t (epsilon) con epsilon cerca de 0.

La pregunta hace más sensible si era t (n) = t (n - sqrt (n)) + m

Answer 2

Tiene razón en que el teorema de Maestros no se aplica aquí. Si mira más de cerca, verá que el costo de la recursión es cero (no hay elemento libre en el lado derecho: T(n) = T(m) + f(n).

Esto significa que no le cuesta absolutamente nada para ejecutar su recursión (ni siquiera 1 operación). Entonces, mientras tu n disminuye sobre las iteraciones (y lo hace porque n > n - sqrt(n)) Su recursión es realmente gratuita.

Entonces la respuesta es O(1). PD: No es posible tener esto en la vida real porque harás al menos o (1) como el costo de la recursión.