우리가 구현한 이진 검색은 O(log2n)의 복잡도를 가진다. 로그 함수에 익숙하지 않다면 기하급수적인 것과 반대되는 개념으로 생각하면 된다. 그래서 로그로 이뤄진 복잡도는 돈과 관련되지 않은 이상 사실 훌륭한 복잡도이다. 이 예에서 정렬 알고리즘이 마법처럼 로그 복잡도를 갖는다면 요소 50만 개로 이뤄진 배열을 정렬하기 위해 단지 18번 정도만 비교하면 된다. 이것은 우리의 이진 검색 구현을 훌륭하게 만든다.
빅오 표기법은 시간 복잡도라고 불리는 계산량 증가를 측정하는 데만 사용되는 것이 아니라 공간 복잡도라고 불리는 메모리 사용의 증가를 측정하는 데도 사용된다. 알고리즘이 빠르더라도, 정렬 예제처럼 메모리가 다항식을 따라 증가할 수 있다. 우리는 이 차이를 이해해야 한다.
Tip ≣
일반적인 생각과는 반대로, O(Nx)는 기하급수적인 복잡도를 의미하지 않는다. 이는 다항 시간 복잡도를 나타내는데, 이것도 꽤 안 좋지만 지수 복잡도만큼 끔찍하지는 않으며 대신 O(xn)으로 표시된다. 단, 항목 100개에 대해 O(N2)은 10,000번을 반복하는 반면, O(2n)은 30자리나 되는 횟수만큼 반복해야 한다. 이 숫자는 읽는 것조차 힘들다. 지수 함수보다 더 심한 요인 복잡도도 있지만, 개인적으로 순열이나 조합을 계산하는 것 외에는 그 어떤 알고리즘도 더 심하지 않았다. 아마 아무도 더 심한 알고리즘을 개발하지 못했기 때문일 것이다.