다음의 C 언어로 작성된 프로그램에서 calc함수의 실행시간(또는 실행… | [국회직 9급 컴퓨터일반] 20년 1회차 기출문제 상세 페이지

calc 함수의 실행 시간은 $O(n^2)$이다.
한 번의 호출에서 for 문이 n번 돌고, 이어서 calc(n - 1)을 호출한다.
$T(n)=T(n-1)+n$
$T(n)=n+(n-1)+\cdots+1=\dfrac{n(n+1)}{2}$
최고차항이 $n^2$이므로 점근 표기는 $O(n^2)$이다.
$O(\log_2 n)$: 호출마다 n이 절반이 아니라 1씩 줄어 호출 깊이만 해도 n이다.
$O(n\log_2 n)$: 호출 깊이가 $\log_2 n$일 때 나오는 형태로, 이 함수의 깊이는 n이다.
$O(n)$: 반복문 없이 재귀 호출만 있을 때의 값으로, 호출마다 도는 for 문의 비용이 빠져 있다.
$O(n^3)$: 삼중 구조일 때의 값으로, 이 함수는 재귀 하나와 단일 for 문뿐이다.