Ordre de compléxité

Bonjour,
Svp est ce qu'il y a quelqu'un qui peut me corrigé cet exercice:
Montrer que les affirmations suivantes sont correctes:

1) n !=O(n puissance n)
ma solution:
n!=1 *(n+1)*(n+2)*.....*(n)<=n*n*....*n=n puissance n.

2)la somme de i=0 à n de i²=Θ(n puissance 3)
ma solution:
la somme de i=0 à n de i²=0²+1²+2²+...+n²>=n* n²=n puissance 3

3)Et pour 5n²-6n ET 2n²+n log n=Θ(n²) je n'ai aucune idée pour prouver que c'est vrai.

Merci d'avance.

Bonjour,

Citation:

---

Envoyé par nadia_inf

1) n !=O(n puissance n)
ma solution:
n!=1 *(n+1)*(n+2)*.....*(n)<=n*n*....*n=n puissance n.

---

Ta formule de factorielle est fausse et par conséquent la majoration aussi. En reprenant la formule exacte de la factorielle, tu pourras majorer chaque facteur par n comme tu l'as fait.

Citation:

---

Envoyé par nadia_inf

2)la somme de i=0 à n de i²=Θ(n puissance 3)
ma solution:
la somme de i=0 à n de i²=0²+1²+2²+...+n²>=n* n²=n puissance 3

---

J'ai l'impression que tu as minoré chacun des termes de ta somme par n, mais cela ce n'est pas possible : on n'a pas 1>=n, 2>=n, etc. Je pense que le plus simple pour répondre à la question est de chercher la formule donnant la somme des carrés des n premiers entiers :
http://www.les-suites.fr/somme-des-n...ers-carres.htm

Citation:

---

Envoyé par nadia_inf

3)Et pour 5n²-6n ET 2n²+n log n=Θ(n²) je n'ai aucune idée pour prouver que c'est vrai.

---

Je ne comprends pas l'énoncé de la question. Peux-tu développer?

1)je pense que pour la formule de factorielle est correct: n! = 1.2.3......(n - 2).(n - 1).n

2)pour la 2eme question c'est bon c'est fait grace au lien que vous m'avez donné.

3)pour la derniere question :je dois montrer que les deux affirmations suivantes sont correctes:
5n²-6n=Θ(n²)
2n²+n log n=Θ(n²)
Mais je ne sais comment minoré

Citation:

---

Envoyé par nadia_inf

3)pour la derniere question :je dois montrer que les deux affirmations suivantes sont correctes:
5n²-6n=Θ(n²)
2n²+n log n=Θ(n²)
Mais je ne sais comment minoré

---

5n²-6n>=cn² <=> 5n-6>=cn <=> (5-c)n>=6 ----> impossible pour c>0

pour la deuxième, il faut étudier les variations de x-log(x) et procéder de façon similaire à précédemment en utilisant le résultat cette étude pour minorer log(n).

Citation:

---

Envoyé par Aleph69

5n²-6n>=cn² <=> 5n-6>=cn <=> (5-c)n>=6 ----> impossible pour c>0

pour la deuxième, il faut étudier les variations de x-log(x) et procéder de façon similaire à précédemment en utilisant le résultat cette étude pour minorer log(n).

---

Bonsoir,

on a quand même n² < 5n²-6n < 5n² pour n>1 donc 5n²-6n est en Θ(n²).

Salut,

exact, j'ai un petit peu oublié de raisonner de façon asymptotique! :aie:

On reprend :

Citation:

---

5n²-6n>=cn² <=> 5n-6>=cn <=> (5-c)n>=6 ----> impossible pour c>0

---

car pour n=1, n obtient (5-c)>=6... sauf qu'il existe toujours un rang N tel que pour tout n>=N, on a bien (5-c)n>=6, quitte à fixer c dans ]0;5[!

Merci kwariz!

Merci beaucoup pour votre aide.