Bonjour !  

il y a quelque temps j'ai eu un contrôle d'algo et même en ayant eu la correction je n'ai pas compris la question suivante :

On considère la fonction f définie sur N par f(n)=(1/2)n^2-5logn+8 cochez le propositions suivantes :

- f(n)=O(1)                -f(n)=théta(nlogn)     -f(n)=Omega(n)

-f(n)=Oméga(n^4)     -f(n)=O(racine(n))     -f(n)=O(n)              

-f(n)=o(n^2)             -f(n)=théta(n^2)       -f(n)=o(n^3)

et les réponses étaient f(n)=théta(n^2),f(n)=Omega(n) et f(n)=o(n^3) mais je ne comprend pas pourquoi ? Pouvez-vous m'aider ???

Bonjour,

voilà l'explication, claire àmha, tirée du Introduction to Algorithms de Cormen, Leiserson, Rivest & Stein :

Une manière de voir les choses est de se souvenir qu'à partir d'un certain moment on a « 𝚯 encadre parfaitement, 𝚶 est toujours au-dessus mais pas forcément en dessous, et 𝛀 est toujours en dessous mais pas forcément au-dessus».

Dans ton exemple, f(n) est dominée par n², du coup elle est en 𝚯(n²) (tu prends comme constante 1 et ¼ par exemple), elle n'est pas en O(1) car pour tout nombre k il existe un n tel que f(n)>k, etc …