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 …
compléxite
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.