로가리즘을 접목해서 빅 오 표기법을 다시 논해 보자. 컴퓨터 과학에서 O(logN)은 사실 O(log₂N)을 줄여 부르는 말이다. 단지 편의를 위해 다음 첨자 2를 생략했을 뿐이다.

앞서 밝혔듯이 빅 오 표기법은 다음과 같은 핵심 질문에 대한 답이다. 데이터 원소가 N개 일 때 알고리즘에 몇 단계가 필요할까?

O(logN)은 데이터 원소가 N개 있을 때 알고리즘에 log₂N단계가 걸린다는 의미다. 원소가 8개이면 log₂8 = 3이므로 이 알고리즘은 3단계가 걸린다.

바꿔 말해 원소 8개를 절반으로 계속해서 나누면 원소가 하나 남을 때까지 3단계가 걸릴 것이다.

이진 검색이 정확히 이렇게 동작한다. 특정 항목을 찾을 때 정답 수에 도달할 때까지 배열의 셀을 계속해서 반으로 나누며 범위를 좁혀 나간다.

간단히 말해 O(logN)은 원소가 하나가 될 때까지 데이터 원소를 계속해서 반으로 줄이는 만큼의 단계 수가 걸린다는 뜻이다.