Explain the answer of this Big O complexity code

Question

for( int bound = 1; bound <= n; bound *= 2 ) { 
    for( int i = 0; i < bound; i++ ) { 
        for( int j = 0; j < n; j += 2 ) { 
            ... // constant number of operations 
        } 
        for( int j = 1; j < n; j *= 2 ) { 
            ... // constant number of operations 
        } 
    } 
}

The correct answer is O(n2). As I understand, the Of the first two for loops, they are "nested". Since bound goes from 1 to n, and i goes to bound. The third and fourth loops are not nested.

The third for loop has complexity O(n+2) , The fourth for loop has complexity O(log n)

Someone told me since n2 > n+2 + log n, algorithm is O(n2). (I'm really confused about this step)

I thought you are suppose to multiply each loop, so shouldn't it be log n(outer loop) * n(2nd outer loop) * n(third) * log N(fourth). how do I know which loop I need to add or multiply, and which loop's value should I take(do I take N over log N for the first two loops because N is smaller to process?

Answer 1

The complexity should be O(n3).

First consider the inner-most loops:

for( int j = 0; j < n; j += 2 ) { 
    ... // constant number of operations 
} 

Index j takes values 0, 2, 4, 6, 8, ... up to n, so j can take at most n / 2 + 1 possible values, hence the complexity of this loop is O(n).

And for another inner-most loop:

for( int j = 1; j < n; j *= 2 ) { 
    ... // constant number of operations 
} 

Index j takes values 1, 2, 4, 8, 16, ... up to n, so j can take at most log(n) + 1 possible values, hence the complexity of this loop is O(log(n)).

Therefore for any fixed bound and i, the total work done by the two inner-most loops is O(n) + O(log(n)) = O(n).

Now consider the two outer-most loops. Note that if the variable bound for the outer-most loop is k, then the loop indexed by i will loop exactly k times.

for( int bound = 1; bound <= n; bound *= 2 ) { 
    for( int i = 0; i < bound; i++ ) { 
        // work done by the inner-most loops
    } 
}

Since bound takes values 1, 2, 4, 8, ..., these two nested loops will loop:

1^2 + 2^2 + 4^2 + 8^2 + ... + (2^?log(n)?)^2

Note that this is just a geometric series with common ratio 4, so the summation gives us:

  ( 4(^(?log(n)?+1) - 1 ) / 3
= O(2^(2log(n))
= O(2^log(n^2))
= O(n^2)

Since the work done of the inner-most loops is independent of these two loops, the total complexity is given by O(n2) * O(n) = O(n3).

Answer 2

The first and second successive innermost loops have O(n) and O(log n) complexity, respectively. Thus, the overall complexity of the innermost part is O(n). The outermost and middle loops have complexity O(log n) and O(n), so a straightforward (and valid) solution is that the overall complexity is O(n^2*log(n))