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

Question

Est-ce que quelqu'un sait comment résoudre cette récidive?

Le théorème de maître ne fonctionne pas ici.

Answer 1

Cela semble évident dans o (1) puisque

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

Par induction, vous obtenez t (n) = t (epsilon) avec Epsilon près de 0.

La question rend plus de sens si c'était t (n) = t (n - sqrt (n)) + m

Answer 2

Vous avez raison de dire que le théorème des maîtres ne s'applique pas ici. Si vous regardez de plus près, vous verrez que le coût de la récursivité est nul (il n'y a pas d'élément gratuit sur le côté droit: T(n) = T(m) + f(n).

Cela signifie que cela ne vous coûte absolument rien pour exécuter votre récursivité (pas même 1 opération). Alors tant que votre n diminue par les itérations (et c'est le cas parce que n > n - sqrt(n)) Votre récursivité est en fait gratuite.

Donc la réponse est O(1). PS Il n'est pas possible d'avoir cela dans la vraie vie parce que vous ferez au moins O (1) comme coût de la récursivité.