N이 증가할 때마다 단계 수가 얼마씩 늘어나는지 살펴보면 대략 N2만큼 늘어남을 알게 된다. 다음 표를 보자.

▼ 표 4-2

버블 정렬의 시간 복잡도를 빅 오 표기법으로 나타내 보자. 빅 오는 데이터 원소가 N개 일 때 알고리즘에 몇 단계가 필요한가라는 핵심 질문에 대한 답이라고 했다.

값이 N개이므로 버블 정렬에는 N²단계가 필요하고, 따라서 빅 오로 나타내면 버블 정렬의 효율성은 O(N²)이다.

O(N²)은 데이터가 증가할 때 단계 수가 급격히 늘어나므로 비교적 비효율적인 알고리즘으로 간주된다. O(N²)을 더 빠른 O(N)과 비교하는 다음 그래프를 보자.

▲ 그림 4-23

데이터가 늘어날수록 O(N²)의 단계 수가 매우 급격히 증가하고 있다. 단순한 대각선을 그리는 O(N)과 비교해 보자.

참고로 O(N²)을 이차 시간(quadratic time)이라고도 부른다.