Loading [MathJax]/jax/output/HTML-CSS/jax.js

Information

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

Συνδεθείτε

[TP.02] Notations - Relations entre fonctions

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)=1000n2+0.001n3.

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

  • f(n)O(g(n))
  • f(n)Ω(g(n))
  • f(n)Θ(g(n))

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


Question 1:
  • f(n)=log(n2)
  • g(n)=log(n)+5
Question 2:
  • f(n)=n
  • g(n)=log(n2)
Question 3:
  • f(n)=10
  • g(n)=log(10)
Question 4:
  • f(n)=2n
  • g(n)=10n2
Question 5:
  • f(n)=log2(n)=log(n)×log(n)
  • g(n)=log(n)