이제 O(N)과 O(1)을 알았으므로 빅 오 표기법이 알고리즘에 걸리는 단계 수를 단순히 22나 400 같은 고정된 수보다 더 의미 있게 표현한다는 것을 알았다. 더 정확히 말해 빅 오 표기법은 머릿속에 새겼던 핵심 질문, 즉 데이터 원소가 N개일 때 알고리즘에 몇 단계가 필요한가에 대한 답이다.

이 핵심 질문이 빅 오의 엄격한 정의는 맞지만 사실 눈에 보이는 것이 전부가 아니다.

데이터가 몇 개든 항상 3단계가 걸리는 알고리즘을 가정하자. 즉 원소가 N개일 때 알고리즘에 항상 3단계가 필요하다. 이를 빅 오로 어떻게 표현할까?

지금까지 배운 지식을 끌어 모아 O(3)이라고 답할 것이다.

하지만 실제로는 O(1)이다. 이유를 알려면 빅 오를 한층 더 깊이 이해해야 한다. 지금부터 설명하겠다.

빅 오는 데이터 원소 N개에 대한 알고리즘의 단계 수를 나타내지만 그것만으로는 “빅 오의 본질”이라는 제목을 따로 붙인 진정한 이유를 파악하기 어렵다.

빅 오의 본질이란 빅 오가 진정으로 의미하는 것, 즉 데이터가 늘어날 때 알고리즘의 성능이 어떻게 바뀌는지를 뜻한다.

이것이 빅 오의 본질이다. 빅 오는 단순히 알고리즘에 필요한 단계 수만 알려주지 않는다. 데이터가 늘어날 때 단계 수가 어떻게 증가하는지 설명한다.