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