알고리즘 시간복잡도 분석 연습문제 풀이

알고리즘 (FOUNDATION OF ALGORITHMS USING JAVA PSEUDOCODE) 책의 연습문제 중 일부입니다. 다음 중첩루프의 시간복잡도 T(n)은?

간략하게 하기 위해서, n이 2의 거듭제곱이라고 가정해도 좋다. 즉, 어떤 양의 정수 k에 대해서, n = 2^k이다. for( I = 1; I <= n; i++){ j = n; while(j >= 1){ // Needs θ(1) ⌊j⌋ = ⌊ j/2 ⌋<- 단위연산 } } n=2이고, i=1일 때, 단위연산 2번 수행. i=2일 때, 단위연산 2번 수행. n=4이고, i=1일 때, 단위연산 3번 수행. i=2일 때, 단위연산 3번 수행. i=3일 때, 단위연산 3번 수행. i=4일 때, 단위연산 3번 수행. n=8일 때, 단위연산 8*4=32번 수행. n=16일 때, 단위연산 16*5=80번 수행.

즉 n = 2^k라고 할 때, i루프는 n번 수행하고, 수행될 때마다 단위연...