Equation de récurence

[black]

Bonsoir,
merci pour votre réponse, je vais regardais ça . Sinon je suis en licence d'informatique, et c'est une matiere appelé mathematiques discrete, d'ou un melange un peu des 2. Sinon mon exercice se partage en 4 parties :
- trouver l'ordre de grandeur asymptotique de T(n)
- Uk=T(2^k) : montrez que Uk verifie la recurence (2)
- resoudre l'equation (2)
- en deduire T(n) en fonction de n lorsque n=2^k

Pour la premiere j'ai donc T(n) de l'ordre de n², et pour la derniere j'ai donc T(n)~4n² . Et je pense avoir donc les elements pour repondre aux 2 questions restantes ! Merci beaucoup de votre aide !

[Luc]

Oki, mais je pense que ce qu'on a fait n'est pas ce que les correcteurs attendent dans la question 1.
En fait, la réponse qu'on a donnée est un autre chemin (le même, en fait) pour répondre directement à 4).

Je suis curieux d'une méthode apparemment rapide pour trouver que T(n) est de l'ordre de n^2.

Luc

[black]

Pour la question 1, j'ai utilisé le theoreme general des equations de recurence, qui pose T(n)=a*T(n/b) + f(n) avec a le nb de sous probleme et n/b la taille, et f(n) le cout de la fusion ... et je me trouve ici dans le cas 3 du theoreme, qui, une fois verifier, dit que T(n)=(~)(f(n)). Ici f(n)=n² donc T(n) a pour ordre de grandeur n² .
Et jutilise effectivements vos premiers posts pour repondre a la derniere question quand n=2^k.