다음 반복문의 시간복잡도는?

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

1. 1

   Θ(log n)

   오답 이유바깥 반복만 세면 Θ(log n)이지만 안쪽 실행 횟수를 합해야 한다.
2. 2

   Θ(n log n)

   오답 이유각 단계에서 안쪽 반복이 항상 n번인 것이 아니므로 Θ(n log n)이 아니다.
3. 3

   Θ(n)

   정답 근거기하급수 합의 마지막 항이 전체 합을 지배하므로 Θ(n)이다.
4. 4

   Θ(n²)

   오답 이유두 반복문 모두 n번 수행되는 구조가 아니므로 Θ(n²)이 아니다.