====== 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 [[wp>Big_O_notation|O]], Ω e Θ.

Data una funzione a valori non negativi //f(n)//, valgono le seguenti proprietà:
  * // ∃ c, n<sub>0</sub> : f(n) ≤ cg(n), ∀ n > n<sub>0</sub> ⇒ f(n) ∈ O(g(n))//
  * // ∃ c, n<sub>0</sub> : f(n) ≥ cg(n), ∀ n > n<sub>0</sub> ⇒ f(n) ∈ Ω(g(n))//
  * // f(n) ∈ O(g(n)) ∧ f(n) ∈ Ω(g(n)) ⇒ f(n) ∈ Θ(g(n))//

[[wp>Big_O_notation|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 [[wp>Best, worst and average case|casi medio, ottimo e pessimo]], che si determinano a parità di dimensione dei dati.