안쪽 변수가 매번 절반으로 줄어드는 다음 중첩 반복문의 시간복잡도는?

for (int i = 1; i <= n; i++) {
    for (int j = i; j > 0; j /= 2) {
        work();
    }
}

1. 1

   O(log n)

   오답 이유O(log n)은 바깥 반복을 빠뜨리고 가장 큰 i에서의 안쪽 반복 횟수만 센 결과다.
2. 2

   O(n)

   오답 이유O(n)은 안쪽 반복을 상수 시간으로 본 결과지만 각 i마다 약 log₂i번 실행된다.
3. 3

   O(n log n)

   정답 근거전체 실행 횟수는 `Σ floor(log₂i)+1`이고 이는 Θ(n log n)이므로 O(n log n)이 정답이다.
4. 4

   O(n²)

   오답 이유O(n²)은 j가 1씩 감소한다고 가정한 값이다. 실제로는 매번 절반이 되어 안쪽 반복이 로그 횟수다.