왜 이진 검색 같은 알고리즘을 O(logN)이라 표현하는지 살펴보자. 우선 로그란 무엇일까?

로그는 로가리즘(logarithm)의 줄임말이다. 먼저 알아 둘 점은 로가리즘과 알고리즘이 매우 비슷하게 보이고 발음되긴 하지만 두 단어는 아무 관련이 없다는 것이다.

로가리즘은 지수(exponent)와 역(inverse)의 관계다. 아주 간단한 예로 지수가 무엇인지 기억을 되살려 보자.

2³은 2 × 2 × 2와 동치로서 값이 8이다.

log₂8은 2³의 역(converse)이다. 즉, 2를 몇 번 곱해야 8을 얻을 수 있는지를 뜻한다.

2를 세 번 곱해야 8이 나오므로 log₂8 = 3이다.

또 다른 예제를 보자.

2⁶을 다음과 같이 표현할 수 있다.

2 × 2 × 2 × 2 × 2 × 2 = 64

2를 여섯 번 곱해야 64가 나오므로 log₂64 = 6이다.