시간 복잡도

알고리즘이 크기 n 인 입력에서 쓰는 기본 연산의 수를 n 의 함수로 나타낸 것이다. 보통 그 크기의 입력 가운데 가장 오래 걸리는 경우(최악의 경우)를 기준으로 삼고, 상수배는 무시한 채 증가율만 본다. 문제의 시간 복잡도는 그 문제를 푸는 가장 빠른 알고리즘의 시간 복잡도를 뜻한다. 위쪽 한계는 알고리즘 하나를 내놓으면 되지만, 아래쪽 한계(하한)는 가능한 모든 알고리즘에 대해 보여야 해서 훨씬 어렵다.