Временная сложность Nested l oop с зависимой переменной и логарифмическим шагом c

Question

Какова временная сложность этого l oop, O(N) или O(N (logN ))

Также вы можете объяснить, как вы вывели

for (int i = 1; i <= n;  i *= 2) {   
    for (int j = 0; j < i; j++) {
        // Statement(s) that take(s) constant time
   }
}

У меня есть объяснение, но оно чувствует себя не так

Answer 1

Я думаю, что вы сбиты с толку из-за утверждения O(n + log(n)), поскольку вы думали, что внешний l oop выполняется logN раз, а внутренний l oop выполняется N раз, поэтому ответ должен быть O(NlogN) , Вы ошибаетесь, потому что внутренний l oop не запускается N раз, он работает только i раз, как объяснено. Теперь, когда вы сложите все i по внешнему l oop, вы получите это 2*2^k - 1 утверждение. Это окажется порядка N, как указано в объяснении.