재귀식 T(n)=2T(n/2)+n, T(1)=1의 점근 시간복잡도는?

1. 1

   O(n)

   오답 이유하나의 레벨 작업량만 보면 n이지만 log n개 레벨을 합쳐야 합니다.
2. 2

   O(n log n)

   정답 근거마스터 정리에서 a=2, b=2이고 n^(log_b a)=n입니다. 결합 비용 f(n)=n이 같으므로 T(n)=Theta(n log n)입니다.
3. 3

   O(n²)

   오답 이유각 레벨 작업량이 증가하지 않으므로 n²까지 커지지 않습니다.
4. 4

   O(log n)

   오답 이유재귀 깊이만 세면 log n이지만 각 단계 전체 작업량 n을 빠뜨렸습니다.