최선의 경우(best case)같은 크기의 입력 중 비교 수가 가장 작다.

최악의 경우(worst case)같은 크기의 입력 가운데 비교 수가 가장 큰 경우로, 어떤 입력의 비용도 이 값을 넘지 않는다.

평균 경우각 입력의 비용에 그 입력의 확률을 곱해 더한다.

목표 위치가 실행 경로를 바꾼다

앞에서부터 비교하고 일치하면 즉시 반환하는 선형 탐색이다.

목록 길이 n

7

목표 위치

4번째

최선첫 위치, 1회

현재 입력

최악

같은 비용표도 확률이 달라지면 평균이 달라진다

위의 목표 위치와 별도로 목록 길이와 입력 분포를 여기서 정한다. 같은 비교 수에 서로 다른 확률을 곱한다.

평균 모형의 목록 길이 n

7

입력 분포반드시 존재, 각 위치가 1/n반드시 존재, 앞쪽일수록 큼없음 1/4, 각 위치가 3/(4n)