Démontrer avec les définitions — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 10)

Démontrer avec les définitions

Complexité des programmes · niveau 2

Énoncé

Pour $n \geq 1$ : $5 n^{3} - 2 n^{2} + 4 \leq 5 n^{3} + 4 n^{3} = 9 n^{3}$ . Et $5 n^{3} - 2 n^{2} + 4 \geq 5 n^{3} - 2 n^{3} = 3 n^{3}$ . Avec $c_{1} = 3$ , $c_{2} = 9$ et $n_{0} = 1$ , on a bien $c_{1} n^{3} \leq f (n) \leq c_{2} n^{3}$ pour $n \geq n_{0}$ .
Supposons $n^{2} \leq c n$ pour tout $n \geq n_{0}$ . Alors $n \leq c$ pour tout $n \geq n_{0}$ , ce qui est faux pour $n = max (n_{0}, c + 1)$ . Donc $n^{2} \in / O (n)$ .
$2^{n + 1} = 2 \times 2^{n}$ : avec $c_{1} = c_{2} = 2$ , $2^{n + 1} \in Θ (2^{n})$ . En revanche, si $2^{2 n} \leq c 2^{n}$ pour $n \geq n_{0}$ , alors $2^{n} \leq c$ pour tout $n \geq n_{0}$ , ce qui est faux. Un facteur constant dans l'exposant change l'ordre de grandeur, un facteur constant devant la fonction ne le change pas.