Exercice 1 : Généralités sur les notations Asymptotiques
Exercice 1 : Généralités sur les notations Asymptotiques
Démontrer que :
- (a) $$n^2 \in \mathcal{O}(10^{-5}n^3)$$
- (b) $$3n^5 + 16n + 2 \in \Omega(n^5)$$
- (c) $$3n^5 + 16n + 2 \in \Theta(n^5)$$
Pour chacun des fonctions Ti(n) suivantes, déterminer sa complexité asymptotique dans la notation Grand-O :
- (d) $$T_1(n) = 6n^3 + 10n^2 + 5n + 2$$
- (e) $$T_2(n) = 3 \log_2(n) + 4$$
- (f) $$T_3(n) = 2n + 6n^2 + 7n$$
Un algorithme de complexité $$\mathcal{O}(n \log n)$$ dans le cas moyen est toujours plus rapide qu'un algorithme dont la complexité est $$\mathcal{O}(n^2)$$ dans le cas moyen. Expliquez la différence entre les notations $$\mathcal{O}()$$ et $$\Omega()$$, sans donner leur définition formelle.
Exercice 2 : Borne Asymptotique (4 pts)
a) Donner les relations d'inclusion entre les ensembles suivants : $$\mathcal{O}(n \log n)$$, $$\mathcal{O}(2^n)$$, $$\mathcal{O}(\log n)$$, $$\mathcal{O}(1)$$, $$\mathcal{O}(n^2)$$, $$\mathcal{O}(n^3)$$ et $$\mathcal{O}(n)$$.
b) Montrer que si $$f(n) \in \mathcal{O}(g(n))$$, alors $$g(n) \in \Omega(f(n))$$.
c) Montrer que si $$f(n) \in \mathcal{O}(g(n))$$, alors $$f(n) + g(n) \in \mathcal{O}(g(n))$$.
d) Montrer que $$f(n) + g(n) \in \Theta(\max(f(n), g(n)))$$.