Dans les questions suivantes, $n$ désigne un nombre entier positif. Il s’agit, par exemple, de la taille d’un problème à résoudre par un algorithme (par ex., trouver la valeur maximale dans un tableau de taille $n$). De plus, $f(n)$ désigne une fonction mathématique qui dépend de $n$, par exemple le nombre d’opérations effectuées lorsque l’on exécute cet algorithme. Cette fonction est parfois décrite de façon explicite, par exemple : $f(n) = 1000n^2 + 0.001n^3$.

Pour chacune des paires de fonction $f(n)$ et $g(n)$ suivantes, précisez si:

• $f(n) \in O(g(n))$
• $f(n) \in \Omega(g(n))$
• $f(n) \in \Theta(g(n))$

Note: Lorsque plusieurs bornes sont acceptables, choisissez toujours la borne la plus stricte possible.