MatteoZan.it

Molto in breve le tre definizioni essenziali di notazione asintotica.

Theta di n, Θ(n) , limite asintoticamente stretto

Θ(g(n))= { f(n) : esistono delle costanti positive c₁, c₂ e n₀ tali che 0 ≤ c₁g(n) ≤ f(n) ≤ c₂ g(n) per ogni n >= n₀}

O grande di n, O(n), limite asintotico superiore

O(g(n))= { f(n) : esistono delle costanti positive c e n₀ tali che 0 ≤ f(n) ≤ c g(n) per ogni n >= n₀}

Omega di n, Ω(n), limite asintotico inferiore

Θ(g(n))= { f(n) : esistono delle costanti positive c e n₀ tali che 0 ≤ cg(n) ≤ f(n) per ogni n >= n₀}