Ký hiệu tiệm cận
Ký hiệu tiệm cận biểu diễn độ phức tạp thuật toán cho phân tích tiệm cận. Ba ký hiệu thường dùng.
Ký hiệu Big-Omega
Big-Omega (Ω) cho ranh giới dưới của f(n) trong nhân tử hằng số.
Ta viết f(n) = Ω(g(n)), nếu tồn tại hằng số dương n₀ và c sao cho, về phía bên phải n₀, f(n) luôn nằm trên hoặc bằng c*g(n).
Ω(g(n)) = { f(n) : Tồn tại c, n₀ dương sao cho 0 ≤ c g(n) ≤ f(n), ∀ n ≥ n₀ }
Ký hiệu Big-Theta
Big-Theta (Θ) cho ranh giới chặt của f(n) trong nhân tử hằng số.
Ta viết f(n) = Θ(g(n)), nếu tồn tại hằng số dương n₀, c₁, c₂ sao cho, về phía bên phải n₀, f(n) luôn nằm giữa c₁*g(n) và c₂*g(n) bao gồm hai đầu.
Θ(g(n)) = { f(n) : Tồn tại c₁, c₂, n₀ dương sao cho 0 ≤ c₁ g(n) ≤ f(n) ≤ c₂ g(n), ∀ n ≥ n₀ }
