빅 오는 특정 방식으로 알고리즘에 필요한 단계 수를 고려함으로써 일관성을 유지한다. 먼저 선형 검색 알고리즘을 빅 오로 나타내 보자.

최악의 경우 선형 검색에는 배열의 원소 수만큼의 단계가 필요하다. 빅 오 표기법으로 표현하는 적절한 방법은 다음과 같다.

O(N)

“빅 오 N”이라고 발음한다. “차수 N”이라고도 부른다. 하지만 이 책에서는 “오 N”이라 부르겠다.

위 표기가 뜻하는 바를 알아 보자. 이 표기는 “핵심 질문”에 대한 답을 나타낸다. 여기서 핵심 질문이란 “데이터 원소가 N개일 때 알고리즘에 몇 단계가 필요할까?”이다. 다시 한 번 읽어 보자. 그리고 머릿속에 선명히 새기자. 이 책 전반에서 사용할 빅 오 표기법의 정의이다.

핵심 질문에 대한 답은 빅 오 표현의 괄호 안에 들어 있다. O(N)은 알고리즘에 N단계가 필요하다는 핵심 질문에 대한 답을 나타낸다.

빅 오 표기법으로 시간 복잡도를 표현하는 사고 과정을 다시 한 번 선형 검색을 통해 간단히 짚고 넘어가자. 먼저 핵심 질문을 던지자. 배열에 원소가 N개일 때 선형 검색에 몇 단계가 필요할까? 선형 검색에는 N단계가 필요하므로 O(N)으로 표현한다. 그래서 O(N)인 알고리즘을 선형 시간(linear time)을 갖는 알고리즘이라고도 부른다.