빅오 표기법은 알고리즘의 효율성을 분류하는 방식으로, 상수 시간 알고리즘은 O(1)이라는 집합에 속해있다. 즉, 어떤 알고리즘이 상수 시간을 가진다면, 그 알고리즘은 O(1)에 속한다고 표현할 수 있다. 마찬가지로, 선형 알고리즘은 O(n) 집합에, 이차 알고리즘은 O(n²) 집합에 속한다. 이처럼 빅오 표기법을 사용하면 알고리즘의 복잡도를 직관적이고 이해하기 쉬운 방식으로 분류할 수 있다.
예를 들어, 상수 시간 알고리즘에 이어 선형 시간 알고리즘을 수행하면 총 실행시간은 선형이 된다.
f ∈ O(n)고 g ∈ O(1)면 f + g ∈ O(n)이 된다
두 개의 선형 연산을 수행하면 합은 여전히 선형이다.
f ∈ O(n)고 g ∈ O(n)면 f + g ∈ O(n)이 된다
k가 n에 의존하지 않는 상수인 한 선형 연산을 k번 수행하면 합은 선형이다.
f ∈ O(n)고 k가 상수면 fk ∈ O(n)이 된다
선형 연산을 n번 반복하면 결과는 이차가 된다.
f ∈ O(n)이면 nf ∈ O(n²)이 된다
일반적으로 n의 가장 큰 지수만 신경쓰기 때문에 총 연산 횟수가 2n + 1이라면 실행시간은 O(n)이다. 선행 상수 2와 덧셈 항 1은 이러한 종류의 분석에서 중요하지 않다. 마찬가지로 n² + 100n + 1000도 O(n²)이 된다. 숫자의 크기는 신경쓸 것 없다.