이 코드를 실행하면 25라는 결괏값이 출력됩니다.

코드 2-1에서 성능을 판단하고 싶은 함수는 func입니다. 매개변수 arr은 리스트이며 init은 초깃값입니다. 단순히 초깃값에 arr의 모든 요소 값을 더한 결괏값을 구하는 함수입니다. 주석에서 func 함수의 연산 횟수를 계산하는 과정을 기술했습니다. 살펴보면 n=len(arr)은 arr 길이를 n에 할당하는 연산입니다. 이 연산은 함수를 통틀어 한 번만 계산됩니다. ret=init도 마찬가지이지요. 우리가 유의해서 보아야 할 곳은 for 문입니다. range()에서 i 값을 반환받는데, 이 연산은 arr 길이만큼 반복됩니다. 즉, 빈도수가 n이 되어 함수가 실행될 때 n번 실행됩니다. ret+=arr[i]도 마찬가지입니다. 최종적으로 얻은 함수의 연산 횟수는 arr 길이 n에 대한 함수 2n+3이 됩니다.

T(n) = 2n + 3

이 예제는 아주 간단하므로 연산 횟수 T(n)을 쉽게 구할 수 있었지만, 일반적인 경우 연산 횟수를 정확하게 기술하기란 쉽지 않습니다. 또 아주 애매한 상황과 마주칠 수 있는데, 다른 함수의 연산 횟수 T(n)=n+500이라면 이 함수는 코드 2-1의 함수 func보다 성능이 좋을까요 나쁠까요? 판단하는 사람에 따라 1차항의 계수가 큰 func 함수에서 arr 길이가 길어질수록 2배만큼 더 연산을 해야 하니 다른 함수가 성능이 좋다고 말할 수도 있을 것입니다. 만약 T(n)=2n+5라면 func 함수가 이 함수에 비해 반드시 성능이 좋다고 말할 수 있을까요?

이런 모호함을 없애고자 알고리즘 성능을 분석할 때는 점근적 표기법을 사용합니다. 많은 사람이 빅오(big-O)로 알고 있는 이 점근적 표기법에는 사실 O-표기법뿐만 아니라 θ-표기법과 Ω-표기법도 있습니다. 이 세 가지 점근적 표기법을 알아보겠습니다.