Khi phân tích thuật toán, chúng ta không chỉ quan tâm đến trường hợp xấu nhất mà còn cần đánh giá toàn diện hành vi của thuật toán ở trường hợp tốt nhất và trường hợp trung bình. Toán học cung cấp 3 ký hiệu tiệm cận chính để chặn thời gian thực thi $T(N)$:
Cho biết thời gian chạy của thuật toán không vượt quá ngưỡng $f(N)$ nhân với hằng số.
Định nghĩa: $T(N) = O(f(N))$ nếu $\exists c > 0, N_0 > 0$ sao cho $T(N) \le c \cdot f(N), \forall N \ge N_0$.
Ý nghĩa thực tế: Lời hứa về "thời gian tối đa" thuật toán sẽ chạy.
Cho biết thuật toán sẽ mất ít nhất bao nhiêu thời gian để hoàn thành.
Định nghĩa: $T(N) = \Omega(g(N))$ nếu $\exists c > 0, N_0 > 0$ sao cho $T(N) \ge c \cdot g(N), \forall N \ge N_0$.
Ý nghĩa thực tế: Giới hạn tối thiểu, không thuật toán nào có thể chạy nhanh hơn ngưỡng này trong trường hợp tốt nhất.
Khi chặn trên $O(f(N))$ và chặn dưới $\Omega(f(N))$ trùng nhau, ta có chặn chặt $\Theta(f(N))$.
Định nghĩa: $T(N) = \Theta(h(N))$ khi và chỉ khi $T(N) = O(h(N))$ và $T(N) = \Omega(h(N))$.
Ý nghĩa thực tế: Biểu diễn chính xác tốc độ tăng trưởng của thuật toán trong mọi trường hợp (hoặc trường hợp trung bình).
Xét hàm tìm một số $X$ trong mảng $N$ phần tử:
Trường hợp tốt nhất: $X$ nằm ở ngay vị trí đầu tiên (arr[0]). Ta chỉ mất đúng 1 phép so sánh $\rightarrow T_{min}(N) = 1 = \Omega(1)$.
Trường hợp xấu nhất: $X$ nằm ở cuối mảng hoặc không tồn tại. Ta phải duyệt hết $N$ phần tử $\rightarrow T_{max}(N) = N = O(N)$.
Trường hợp trung bình: $X$ nằm ở giữa mảng. Ta mất $\frac{N}{2}$ phép so sánh $\rightarrow T_{avg}(N) = \Theta(N)$ (vì bỏ hằng số $\frac{1}{2}$).