Preuve Big-O pour une relation de récurrence?

8

Cette question est assez spécifique dans la manière de prendre les mesures pour résoudre le problème.

Donné T(n)=2T(2n/3)+O(n) prouve-le T(n)=O(n2).

Les étapes étaient donc les suivantes. Nous voulons prouver queT(n)cn2.

T(n)=2T(2n/3)+O(n)2c(2n/3)2+unen(8/9)(cn2)+unen
puis mon prof a continué à faire:

T(n)cn2+(unen-(1/9)cn2),
ce qui revient à:

T(n)cn2 pour toute c> =9une.

Ma question est, comment ont-ils pu passer du 8/9 au 1/9 tout en introduisant un nouveau terme? Est-ce permis? Elle n'a jamais expliqué, c'était juste dans ses solutions.

D. Johnson
la source
2
Je ne vois pas de nouveau terme introduit? Nous avons çacn2+unen-(1/9)cn2 simplifie à (8/9)cn2+unencomme dans la ligne précédente. Donc, les deux lignes sont en fait égales. Peut-être vous demandez-vous pourquoi on pourrait vouloir faire cela?
user340082710
Je suppose également que la dernière ligne doit se lire cn2 par opposition à ck2.
user340082710
@ZacharyFrenette Ah tu as raison. dans ce cas, je ne savais pas trop comment elle avait fait la simplification. Pourquoi choisirait-on de séparer les termes de cette façon? il existe de nombreuses façons de diviser (8/9). Je pense que je sais pourquoi on voudrait faire ça, annuler ce supplémentunen? Sinon, l'inégalité ne tiendra pas. Merci aussi d'avoir souligné la faute de frappe, cela va corriger. si vous souhaitez commenter comme réponse, je peux l'accepter.
D. Johnson

Réponses:

12

Comme vous l'avez souligné, la raison de la scission du terme en deux parties est de pouvoir annuler la unenterme. Si nous allons directement de(8/9)cn2+unencn2+unen, alors nous sommes coincés car nous ne pouvons rien faire avec le unenterme. En le divisant de la manière décrite, cela permet au(1/9)cn2 être plus grand que unen quand c9une, qui vous donne alors le résultat souhaité puisque unen-(1/9)cn20 pour de telles valeurs de c.

user340082710
la source