5

I'm new to Java, my question is on big-O complexity.

For a), it is clearly O(n^2) for a nested loop.

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

however, for b), with sum++ operation at the end, and complications in the nested loop, does that change the 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++;
ntalbs
  • 28,700
  • 8
  • 66
  • 83
Katherine
  • 257
  • 2
  • 6
  • 15
  • On a side note also check this: http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it – Rahul Tripathi May 13 '15 at 08:49
  • Those constant time operations within the loop contribute to the terms which are dropped in the estimation. – ChiefTwoPencils May 13 '15 at 08:52
  • Note that unless you have a hidden expensive operation (such as `get()` on a `LinkedList`) that's a result of an invalid assumption about a library, the language is irrelevant for big-O analysis. – chrylis -cautiouslyoptimistic- May 13 '15 at 08:57
  • Just a note: It is not just related to Java but algorithm itself so its language independent. All constant time operations have complexity of O(1) – Nitin Dandriyal May 13 '15 at 08:58
  • What you should ask yourself is how many times the inner loop will run given a value of `n`. You see that if n = 10, it'll run 4 times, for n = 100, 7 times, for n = 1000, 10 times. So you see that's already not linear. Then you can use some mathematical algebra for a formal proof, but you have already an idea of what it shouldn't be (such as O(n^2)). – Alexis C. May 13 '15 at 09:00

4 Answers4

7

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

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

Matt
  • 17,290
  • 7
  • 57
  • 71
ntalbs
  • 28,700
  • 8
  • 66
  • 83
1

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

Note, this is not specific to Java - it would be the same in any other language :-)

Cheers,

Anders R. Bystrup
  • 15,729
  • 10
  • 59
  • 55
1

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

For the nested loop:

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

2) The outer loop stays roughly the same having O(n-1) which is equal to O(n) as constant terms can always be neglected in asymptotic calculations.

3) The inner loop takes log2(n) steps to finish. In every step n is reduced to its half, therefore multiplying by 2 takes one step back, which leads to the binary logarithm.

In summary, the complexity is O(n log2(n))

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

gapvision
  • 999
  • 1
  • 10
  • 30
  • Hi how did you determine the inner loop takes log2(n)? – Katherine May 13 '15 at 09:19
  • if you look at the loop, the steps are `j`, `j/2`, `j/4`, `j/8` ... In the reverse direction, you would have to multiply each step with `2` to get to the next. At most, this can take `n` steps which would result in `2^n` for the reverse direction. To come back to our origin loop, we need to take the inverse function of the exponential function, which is the logarithm... – gapvision May 13 '15 at 09:52
  • Thanks! :) one more question, what happen when the outer loop is as follows: for ( int i = 1; i <= n * n; i++) does that make it O(n^2) because of i – Katherine May 13 '15 at 11:02
  • yepp, `O(n^2)` would be the complexity of the outer loop – gapvision May 13 '15 at 11:19
0

Speaking from a purely computer science point of view, the big O(see the definition), describes a worst case scenario. This even means if you half the inner for loop, the O(n^2) still applies. However you can write it as a less rising function.

Radovan
  • 142
  • 1
  • 10