Big-O Nested Loops

Question

Trying to understand Big O and nested loops i've been going through the notes and can't understand how the nested loop part of this question works...I have an answer of 6 + 1.5n + nlogn wrote down from lectures but don't understand how to get the n log n part

    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;
     } 
    }

My understanding is the 6 is from the six statements not inside a loop and the 1.5n comes from 3(n-1 + n-2 +....1)/2 so if someone could help with the last part or correct me if im wrong it would be greatly appreciated

Part 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

Well, I guess, there´s a typo in the question, the inner loop should be

// 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 )

in that case, the outer loop

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

brings 2 * n, while the inner one (notice j = 2 * j)

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

results in just log(n); finally (since loops are nested we should multiplicate complexities) we have

O(n * log(n))