조금 더 나아가 n개의 데이터를 수행하는 데 걸리는 시간이 제곱만큼, 즉 (충분히 큰 값인 n과 상수 c에 대해) f(n) = 4n² + 4n + 1이라고 한다면 동일 최대 차수인 최소 단위 시간 복잡도 g(n) = n²이 있을 때 f(n) ≤ cg(n)이 성립하는 상수 c가 존재하므로 결론적으로 표기법 O(x)를 사용하여 최소 단위인 O(n²)으로 표현할 수 있습니다.

빅오 표기법을 사용하니 실제로 소요되는 시간의 최고 차항만 남았군요. 왜 이럴까요? 앞서 언급했던 ‘충분히 큰 값’은 입력 개수가 100개, 200개 정도의 적은 데이터가 아니라 10만 개, 100만 개 수준이므로 4n²과 4n을 비교하면 연산 횟수가 400억 vs 40만 정도로 차이나기 때문에 작은 수는 상대적으로 무시할 수 있어 최고 차항 미만의 연산은 전체 소요 시간에 큰 영향을 줄 수 없습니다.

▲ 그림 2-1 차수별 시간 복잡도 비중

즉, 연산 횟수가 최고 차항에 비례하는 흐름을 보인다면 부가적인 연산은 신경 쓸 필요가 없습니다. 가령 n² + 2n + 1의 시간 복잡도 역시 최고 차항만 계산하여 O(n²)으로 줄어듭니다. 같은 이유로 99n의 시간 복잡도는 O(n)으로 줄어듭니다.