Big-O Java Interface

Question

I am new to Java, my question is very complex.

For a), explicitly O(n^2) for the nested loop.

 for ( int i = 0; i < n; i++) for ( int j=0; j < n; j++ ) 

however, for b), with the sum ++ operation at the end and complications in the nested loop, does this alter its Big-O complexity at all?

 int sum = 0; for ( int i = 1; i <= n; i++) for ( int j = n; j > 0; j /= 2) sum++; 

Answer 1

Well, first: Big O notation is not related to the programming language, it depends only on the implementation. Therefore, it doesn’t matter if you run loops in Java or in any other language (besides some optimizations performed by the interpreter / compiler, which, however, will change the program flow)

For a nested loop:

1) sum++ considered as a constant operation with a cost of 1 . Therefore, it can be neglected. O(n * 1) = O(n)

2) The outer cycle remains approximately the same as O(n-1) , equal to O(n) , since the constant terms can always be neglected in asymptotic calculations.

3) The inner loop requires steps log2(n) . At each step, n reduces to its half, therefore, multiplication by 2 occurs one step back, which leads to a binary logarithm.

So the complexity is O(n log2(n))

EDIT: the funny thing: so far no one has seen that the inner loop has real O(infinity) complexity, since division of some positive number is always greater than 0 ... Or am I wrong here?

Answer 2

In your second example, the first for iteration is n times, and the second iteration is log2(n) times, since you divide j by 2 at each iteration. Therefore, the complexity is O (n log2 n).

sum++ in the last line does not affect complexity.

Answer 3

Obviously, in your example b), the inner loop does fewer iterations than in a). Decreasing the iteration counter at each iteration is essentially a logarithmic (log2) operation, so the O-complexity of example b) is O( n log2(n)) .

Please note that this does not apply to Java - it would be the same in any other language :-)

Greetings

Answer 4

Speaking from the point of view of purely computer science, large O (see definition) describes the worst case scenario. It even means that if you use half the inner loop, O (n ^ 2) is still applicable. However, you can write it as a less upstream function.