Course list Sign in

Information

Author(s) Vincent Branders, Pierre Dupont
Deadline 28/02/2024 14:00:00
Submission limit No limitation

Sign in

Sign in

[TP.02] Notations - Vrai ou faux ?

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 les questions ci-dessous, indiquez si les affirmations sont vraies ou fausses.

Question 1:

\(1000{n}^{2}+0.001 {n}^{3} \in \Theta({n}^{3})\)

Question 2:

\(n\log(n) \in O(n)\)

Question 3:

\(n^2 \in \Omega(n)\)

Question 4:

\(10^{12} \in O(1)\)

Question 5:

\(0.00001 \in \Theta(1)\)

Question 6:

\(400n^3 - 10n \in \Theta(n^3)\)

Question 7:

\(n^3 + \log n \in \Omega(n)\)

Question 8:

\(2^{n+1} \in \Theta(2^n)\)

Question 9:

\(2^{n+3} + \log n \in O(2^n)\)

Question 10:

\(2^{2n} \in O(2^n)\)

Question 11:

\(3^n \in O(2^n)\)

Question 12:

\(\log_2 n \in \Theta(\log_{10} n)\)

Question 13:

\(\sqrt{n} \in \Theta(\log n)\)

Question 14:

\(3n^2 + \sqrt{n} \in O(n^2)\)

Question 15:

\(f(n) \in O(n) \Rightarrow f(n) \in \Omega(n)\)

Question 16:

\(f(n) \in \Omega(n) \Rightarrow f(n) \in O(n)\)

Question 17:

\(f(n) \in \Omega(\log n) \Rightarrow f(n) \in \Theta(\log n)\)

Question 18:

\(f(n) \in \Theta(n^3) \Rightarrow f(n) \in \Omega(n^3)\)

Question 19:

\(f(n) \in \Omega(n^2) \Rightarrow f(n) \in \Omega(n)\)

Question 20:

\(f(n) \in \Omega(n) \mbox{ et } f(n) \in \Theta(n) \Leftrightarrow f(n) \in O(n)\)