Notazioni O, Ω e Θ

Nella lezione del 29/10 abbiamo concluso la discussione della complessità computazionale, introducendo tre notazioni che caratterizzano le classi di complessità: le notazioni O, Ω e Θ.

Data una funzione a valori non negativi f(n), valgono le seguenti proprietà:

• ∃ c, n₀ : f(n) ≤ cg(n), ∀ n > n₀ ⇒ f(n) ∈ O(g(n))
• ∃ c, n₀ : f(n) ≥ cg(n), ∀ n > n₀ ⇒ f(n) ∈ Ω(g(n))
• f(n) ∈ O(g(n)) ∧ f(n) ∈ Ω(g(n)) ⇒ f(n) ∈ Θ(g(n))

O e Ω stabiliscono dei limiti superiore e inferiore per la complessità di un dato algoritmo. Si noti che questi limiti riguardano la crescita asintotica del costo computazionale al crescere della dimensione dei dati, e non invece i casi medio, ottimo e pessimo, che si determinano a parità di dimensione dei dati.