Вложенные петли Big-O

Question

Попытка понять Big O и вложенные циклы Я просматривал заметки и не могу понять, как работает эта часть вложенного цикла ... У меня есть ответ 6 + 1.5n + NlogN записывала из лекций, но не понимает, как получить н лог н часть

Simple Statement; 
    Simple Statement; 
    Simple Statement; 
    Simple Statement; 
    for (int i = 0; i < (n/2); i++) { 
     Simple Statement; 
     Simple Statement; 
     Simple Statement; 
    } 
    Simple Statement; 
    Simple Statement; 
    for (int i = 0; i < 2 * n; i++) { 
    for (int j = 0; j < n; j = 2 * j) { 
     Simple Statement; 
     Simple Statement; 
    } 
    } 

насколько я понимаю, 6 от шести утверждений не внутри цикла и 1.5N приходит от 3 (n- 1 + n-2 + .... 1)/2, так что если кто-то может помочь с последней частью или исправить меня, если я ошибаюсь, было бы весьма полезно

Часть im stuck on:

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

Answer 1

Ну, я думаю, There'sa опечатка в вопросе, внутренний цикл должен быть

// notice "j = 1", not "j = 0", 
// otherwise you have an infinite loop, since 0 * 2 == 0 
for (int j = 1; j < n; j = 2 * j) 

в этом случае внешний контур

for (int i = 0; i < 2 * n; i++) 

приносит 2 * n, а внутренний (уведомление j = 2 * j)

for (int j = 1; j < n; j = 2 * j) 

всего лишь log(n); наконец (поскольку циклы вложенными мы должны мультипликативной сложности) мы имеем

O(n * log(n)) 

Answer 2

Итерация от 0 to 2*n приведет к сложности O(N). Итерация от 0 to n, имеющая мощность шагов 2, приведет к сложности O(log(N)). Умножение этих двух сложностей приведет к окончательной сложности O(N * log(N)).