다음 설명에 해당하는 복잡도 함수에 대한 시간 복잡도는?○ T(1)=2… | [7급 국가직 알고리즘] 23년 1회차 기출문제 상세 페이지

시간 복잡도는 $\Theta(n^2)$이다.
마스터 정리 적용: $a=9,\ b=3,\ f(n)=8n$
$n^{\log_b a}=n^{\log_3 9}=n^2$
$f(n)=8n=O(n^{2-\epsilon})$ ($\epsilon=1$)이므로 첫째 경우에 해당해 $T(n)=\Theta(n^2)$이다. 초기값 T(1)=27은 상수배에만 영향을 준다.
$\Theta(1)$은 n과 무관한 상수 시간으로, 재귀 호출이 9개씩 늘어나는 이 식과 맞지 않는다.
$\Theta(\log_2(n))$은 $T(n)=T(n/2)+c$처럼 부분 문제가 하나일 때의 결과다.
$\Theta(n)$은 비재귀 항 8n만 본 것으로, 지배적인 재귀 부분 $n^2$를 놓친 값이다.