Kursliste Logg inn

Informasjon

Forfatter(e) Vincent Branders, Pierre Dupont
Frist 25/02/2026 14:00:00
Innleveringsgrense Ingen begrensning

Logg inn

Logg inn

[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.

Spørsmål 1:

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

Spørsmål 2:

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

Spørsmål 3:

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

Spørsmål 4:

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

Spørsmål 5:

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

Spørsmål 6:

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

Spørsmål 7:

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

Spørsmål 8:

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

Spørsmål 9:

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

Spørsmål 10:

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

Spørsmål 11:

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

Spørsmål 12:

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

Spørsmål 13:

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

Spørsmål 14:

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

Spørsmål 15:

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

Spørsmål 16:

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

Spørsmål 17:

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

Spørsmål 18:

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

Spørsmål 19:

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

Spørsmål 20:

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