Definizioni delle notazioni asintotiche più comuni
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 c1, c2 e n0 tali che 0 ≤ c1g(n) ≤ f(n) ≤ c2 g(n) per ogni n >= n0}
O grande di n, O(n), limite asintotico superiore
O(g(n))= { f(n) : esistono delle costanti positive c e n0 tali che 0 ≤ f(n) ≤ c g(n) per ogni n >= n0}
Omega di n, Ω(n), limite asintotico inferiore
Θ(g(n))= { f(n) : esistono delle costanti positive c e n0 tali che 0 ≤ cg(n) ≤ f(n) per ogni n >= n0}
Tags: algorithms, math