입력 크기를 고정하기
입력 길이 n을 고정한 뒤 가능한 입력별 비용 가운데 최댓값을 살핀다. 서로 다른 크기의 입력을 한데 모아 가장 오래 걸리는 것을 고르는 뜻은 아니다. n이 변할 때 최악 비용 함수가 어떻게 증가하는지 분석한다.
선형 탐색의 예
n개 원소를 앞에서부터 찾는 선형 탐색에서는 목표가 없거나 마지막에 있을 때 모든 원소를 확인한다. 한 번의 원소 비교를 기본 연산으로 보면 최악의 비교 횟수는 n이다.
상한과의 관계
최악 비용이 모든 허용 입력의 비용을 제한하므로 자원 예산을 검토하는 데 유용하다. 다만 빅오 표기는 최악 분석 그 자체가 아니라 선택한 비용 함수의 점근적 상한을 나타내는 기호다.
평균과 구별
최악 입력이 드물더라도 그 입력을 허용한다면 최악 분석에 포함한다. 반대로 최악 비용이 크다는 사실만으로 일반 입력도 항상 느리다고 결론낼 수 없다. 실제 입력 분포와 평균 비용은 별도로 살펴야 한다.
관련 문서
시간 복잡도 / 공간 복잡도 / 빅오 표기법 / 평균의 경우 분석 / 선형 탐색 / 알고리즘 / 분할 상환 분석