CODEWITHSUNDEEP
algorithmdata-structuresnested-loopsbig-o
Cillian Hughes
Cillian Hughes

Reputation: 47

Big-O Nested Loops

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

Upvotes: 2

Views: 350

Answers (2)

Iulian Popescu
Iulian Popescu

Reputation: 2643

Iterating from 0 to 2*n will result in a complexity of O(N). Iterating from 0 to n having the steps power of 2 will result in a complexity of O(log(N)). Multiplying this 2 complexities will result in a final complexity of O(N * log(N)).

Upvotes: 2

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186668

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

Upvotes: 5

Related Questions