2장에서는 정렬된 배열에서 이진 검색이 선형 검색보다 훨씬 빠름을 배웠다. 이제 이진 검색을 빅 오 표기법의 관점에서 어떻게 설명하는지 알아보자.

데이터가 커질수록 단계 수가 늘어나므로 이진 검색은 O(1)이라 표현할 수 없다. 또한, 검색하고 있는 원소 수보다 단계 수가 훨씬 적으므로 O(N)의 부류에도 맞지 않는다. 앞서 본대로 이진 검색은 100개의 원소를 포함하는 배열에서 7단계만 걸린다.

이진 검색은 O(1)과 O(N) 사이 어디쯤엔가 있다. 이를 어떻게 나타낼까?

빅 오는 이진 검색의 시간 복잡도를 다음과 같이 설명한다.

O(logN)

“오 로그 N”이라고 읽는다. 이러한 유형의 알고리즘을 로그 시간(log time)의 시간 복잡도라고 말한다.

간단히 말해 O(logN)은 데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 알고리즘을 설명하는 빅 오의 방법이다. 2장에서 배웠던 대로 이진 검색이 바로 그렇다. 왜 O(logN)으로 표현하는지 곧 알아보겠지만 먼저 지금까지 배운 내용을 요약해 보자.