6행은 알고리즘이 대부분 시간 동안 실행하는 연산이므로 (n(n + 1))/2은 최악의 경우일 때 알고리즘의 실행 시간이 된다.

알고리즘의 실행 시간을 이야기할 때 실제 관심은 입력 데이터 n이 클 때의 실행 시간이다. 즉, 입력 데이터가 무한히 증가할 때 알고리즘이 어떻게 작동하는가를 다루는 점근적 실행 시간(asymptotic running time)이 실제 관심 대상이다. 알고리즘의 점근적 실행 시간은 특별한 표기법을 사용하여 표현한다. 어떤 양의 초깃값보다 큰 모든 n에 대해 임의의 함수 f(n)이 또 다른 함수 g(n)을 양의 상수 c로 스케일링한 cg(n)보다 작거나 같을 때 O(f(n)) = g(n)이라고 한다. 좀 더 정확히 말해, 모든 n ≥ n₀에 대해 0 ≤ f(n) ≤ cg(n)인 양의 상수 c와 n₀가 있으면 O(f(n)) = g(n)이라고 한다.

여기서 O(f(n))을 빅오 표기법(big O notation)이라고 부르는데, 아주 큰 입력 값이 알고리즘의 성능 차이를 측정할 수 있는 핵심이 되기 때문에 입력 데이터 중에서 큰 값이 관심 대상이 된다. 그림 1-2를 보면 f₁(n) = 20n + 1000과 f₂(n) = n²이라는 두 함수가 있다. 그림에서 n 값이 작을 때는 f₁(n)이 크지만, 초반 이후로 상황이 급격하게 변화하며 n²이 아주 빠르게 증가하는 것을 볼 수 있다.

▲ 그림 1-2 O(f(n)) 비교