Someone explain me some steps of this Java Big O 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 (n ^ 2).

I know that for the third cycle, the cycle has complexity O (n + 2), the fourth for the cycle has complexity O (log n), since the two loops are not nested, are they added together correctly? So what should I do with the first two loops, I know this is log (n) and n. so my question is what the next step should be, how to find out which cycle to add or propagate. Basically, I'm just confused as they get to O (n ^ 2).

Answer 1

The bound value in the first loop doubles each iteration to n : 1, 2, 4 ... n

The second cycle starts to the bound value, adding: 1 + 2 + 4 + ... + n = O(n)

The third and fourth cycles O(n) and O(logn) , which are added together, are simply O(n) , because n dominates logn .

So, the first two loops together are O(n) , and the inner two loops are O(n) . Multiplied together, they are O(n^2) .

Answer 2

The rules for O are O (a + b) = O (max (a, b)), O (const * a) = O (a). (max is not as complex as in actual numbers)

So, the innermost loops are O (n), together they are O (n + n) = O (max (n, n)) = O (n).

The middle loop is O (n), but the outer is O (log n), which is output as O (n * n * log n). This is not an O error - this is only the upper limit for operations, all O (n) is O (n * n).

But we can do better!

Each time the middle cycle is executed, it doubles the number of operations performed. it starts when 1 next - 2, 4, 8, etc. together, both the middle and the outermost cycle perform operations 1 + 2 + 4 + 8 + ... + n. it is O (n + m - 1), where m is the first power of two after n - 1, but because of this n <= m <2 * n, so m = O (n), O (n + m) = O (n + n) = O (n)

therefore, the extreme and middle loops together represent O (n), and the innermost one is O (n), which means that all this is O (n * n) or O (n ^ 2), as you wrote