문제 1에서 배운 1부터 n까지의 합을 구하는 공식에 n 대신 n-1을 대입하면 다음과 같습니다.

 

 

번 비교해야 한다는 것을 알 수 있습니다. 대문자 O 표기법으로는 O(n²)이라고 표현합니다. n의 제곱에 비례해서 계산 시간이 변하는 것이 핵심이므로 n² 앞의 계수   이나   은 무시하고 O(n²)으로 표현한 것입니다.

계산 복잡도가 O(n²)인 알고리즘은 입력 크기 n이 커지면 계산 시간은 그 제곱에 비례하므로 엄청난 차이로 증가합니다. 알고리즘 분석에 대문자 O 표기법이 중요한 이유는 이렇게 입력 크기가 커질 때 계산 시간이 얼마나 증가할지 가늠해 볼 수 있기 때문입니다.