Lower Bound và Tight Bound thường được sử dụng để mô tả các giới hạn của độ phức tạp thuật toán, nhưng chúng có ý nghĩa khác nhau:
Lower Bound (Giới hạn dưới)
Lower Bound là giới hạn dưới của độ phức tạp thời gian hoặc không gian của một thuật toán, cho biết thuật toán không thể thực hiện nhanh hơn hoặc sử dụng ít tài nguyên hơn giới hạn này. Nói cách khác, đây là cận dưới của hiệu suất tốt nhất có thể đạt được bởi bất kỳ thuật toán nào giải quyết vấn đề cụ thể.
Tight Bound (Giới hạn chặt)
Tight Bound là khi giới hạn dưới (lower bound) và giới hạn trên (upper bound) của độ phức tạp thuật toán là như nhau, hoặc rất gần nhau, cho thấy rằng đánh giá độ phức tạp là chính xác và không thể cải thiện thêm. Khi một thuật toán có tight bound, điều này có nghĩa là độ phức tạp thời gia...
