6

Can anyone please let me what would be big O time complexity for the following piece of code:

for (int i = 0; i < array.length - 1; i++) {
    for (int j = i + 1; j < array.length; j++) {
        // do something
    }
}

It can't be O(n^2) since j = i + 1 ? Thanks!

robosoul
  • 757
  • 7
  • 17

1 Answers1

13

There are n-1 iterations of the outer loop. On each iteration, the inner loop iterates n-i-1 times. So in total the inner loop iterates n-1 + n-2 + ... + 1 times. So the number of times that do something executes is equal to the sum of the numbers from 1 to n-1. That sum is n*(n-1)/2, which is in Theta(n^2) and thus also in O(n^2).

sepp2k
  • 363,768
  • 54
  • 674
  • 675
  • 1
    This link may provide some more helpful information: http://stackoverflow.com/questions/12779055/big-o-notation-does-more-complex-mean-faster-or-slower – dcaswell Aug 27 '13 at 08:02
  • sepp2k, thanks a lot for the explanation. @user814064, thanks for the link, it's really helpful. – robosoul Aug 28 '13 at 09:20
  • I don't understand why we don't multiply inner sum of iterations with the outer loop. `n*(n*(n-1)/2)`. We do that if j starts with 0 all the time to get n*n – sidoshi Aug 27 '18 at 13:08
  • 1
    @sidoshi You can't both multiply and sum like that - in either case. When `j` starts at 0, you get `n + ... + n`, which equals `n*n`. When `j` starts at `i+1`, you get `n-1 + ... + 1`, which equals `n*(n-1)/2`. In either case you can either use the sum or the closed form. You don't multiply the closed form by `n` - if you did that, you'd get `n^3` for the case that `j` starts at 0. – sepp2k Aug 27 '18 at 17:43
  • I understand it now. Thanks :) – sidoshi Aug 27 '18 at 17:50