Có nhiều trường hợp, thời gian thực hiện giải thuật không phải chỉ phụ thuộc vào kích thước dữ liệu mà còn phụ thuộc vào tình trạng của dữ liệu đó nữa. Chẳng hạn thời gian sắp xếp một dãy số theo thứ tự tăng dần mà dãy đưa vào chưa có thứ tự sẽ khác với thời gian sắp xếp một dãy số đã sắp xếp rồi hoặc đã sắp xếp theo thứ tự ngược lại. Lúc này, khi phân tích thời gian thực hiện giải thuật ta sẽ xét trường hợp tốt nhất, trường hợp trung bình và trường hợp xấu nhất.
- Phân tích thời gian thực hiện giải thuật trong trường hợp xấu nhất (worst-case analysis): với một kích thước dữ liệu n, tìm T(n) là thời gian lớn nhất khi thực hiện giải thuật trên mọi bộ dữ liệu kích thước n và phân tích thời gian thực hiện giải thuật dựa trên hàm T(n).
- Phân tích thời gian thực hiện giải thuật trong trường hợp tốt nhất (best-case analysis): với một kích thước dữ liệu n, tìm T(n) là thời gian ít nhất khi thực hiện giải thuật trên mọi bộ dữ liệu kích thước n và phân tích thời gian thực hiện dựa trên hàm T(n).
- Phân tích thời gian trung bình thực hiện giải thuật (average-case analysis): giả sử rằng dữ liệu vào tuân theo một phân phối xác suất nào đó (chẳng hạn phân bố đều nghĩa là khả năng chọn mỗi bộ dữ liệu vào là như nhau) và tính toán giá trị kỳ vọng (trung bình) của thời gian chạy cho mỗi kích thước dữ liệu n (T(n)), sau đó phân tích thời gian thực hiện giải thuật dựa trên hàm T(n).
Khi khó khăn trong việc độ phức tạp tính toán trung bình (bởi việc xác định T(n) trung bình thường phải dùng tới những công cụ tính toán phức tạp), người ta thường chỉ đánh giá độ phức tạp tính toán trong trường hợp xấu nhất.
Không nên lẫn lộn các cách phân tích trong trường hợp xấu nhất, trung bình, và giá tốt nhất với các ký pháp biểu diễn độ phức tạp tính toán, đây là 2 khái niệm hoàn toàn phần biệt.
Trên phương diện lý thuyết, đánh giá bằng ký pháp Θ(.) là tốt nhất, tuy vậy việc đánh giá bằng ký pháp Θ(.) đòi hỏi phải đánh giá bằng cả ký pháp O(.) lẫn Ω(.). Dẫn tới việc phân tích thuật toán khá phức tạp, gần như phải biểu diễn chính xác thời gian thực hiện giải thuật qua các hàm giải tích. Vì vậy trong những thuật toán người ta thường dùng ký pháp T(n) = O( f(n)).
5. Chi phí thực hiện thuật toán.
- Khái niệm độ phức tạp thuật toán đặt ra không chỉ dùng để đánh giá chi phí thực hiện một giải thuật về mặt thời gian mà là để đánh giá chi phí thực hiện giải thuật nói chung, bao gồm cả chi phí về thời gian ( lượng bộ nhớ cần sử dụng).
- Thông thường:
Nếu ta đánh giá được độ phức tạp tính toán của một giải thuật qua ký pháp Θ, có thể coi phép đánh giá này là chủ chặt và không cần đánh giá qua các ký pháp khác nữa.
Nếu không:
+ Để nhấn mạnh tính “tốt” của một giải thuật, các ký pháp O, o thường được sử dụng. Nếu đánh giá được qua O thì không cần đánh giá qua o. Ý nói: chi phí thực hiện thuật toán tối đa là …, ít hơn….
+ Đề cập đến tính toán “tồi” của một giải thuật, các ký pháp Ω, ω thường được sử dụng. Nếu đánh giá được qua Ω thì không cần đánh giá qua ω. Ý nói chi phí thực hiện thuật toán tối thiểu là…, cao hơn…