Thuật ngữ được đưa ra cho thuật toán tương ứng giả sử rằng T đại diện cho một đơn danh trong T (n) là gì?
Nếu kích thước đầu vào là n, thời gian thực hiện có thể được biểu thị như là một hàm của n. Kể từ khi thời gian thực hiện trên các đầu vào khác nhau có cùng kích thước có thể khác nhau, trường hợp xấu nhất thời gian phức tạp T(n) được định nghĩa là thời gian tối đa thực hiện trên tất cả các đầu vào có kích thước n. Nếu T(n) là một đa thức trong n, sau đó thuật toán được cho là một thuật toán thời gian đa thức. Luận án của Cobham nói rằng một vấn đề có thể được giải quyết với một số lượng khả thi của các nguồn lực nếu nó thừa nhận một thuật toán thời gian đa thức.