0

Could you please help me to clarify what is the complexity of the following piece of code where I traverse through the "unvisited" items in an array on each step?

final int[] arr = {...};
for (int i = 0, length = arr.length; i < length; i++) {
    System.out.print(arr[i]);
    for (int j = i + 1; j < length; j++) {
        System.out.print(arr[j]);
    }
}

I bet it's O(NlogN) or O(N√N), where N is arr.length

Am I right? Could you explain to me why?

I think it's O(NlogN) or O(N√N) because on each step the "unvisited" part is reduced so it's less than O(N^2) but still greater than O(N)

Pasha
  • 1,768
  • 6
  • 22
  • 43
  • 2
    Why don't you explain why you think it's `O(log N)` – MFisherKDX Apr 03 '19 at 00:55
  • I've updated my question – Pasha Apr 03 '19 at 00:58
  • It's not O(log N), it's n(n+1)/2 => n^2 in short. Where n(n+1)/2 is sum of n natural numbers. – Juseeth Apr 03 '19 at 01:01
  • It is `O(n^2)`. The second loop runs on average `n/2` times, and constant multipliers are ignored. – shmosel Apr 03 '19 at 01:01
  • You have to think about what the biggest polynomial term would look like if you wrote it out – Zigzagoon Apr 03 '19 at 01:02
  • Detailed explanation [here](https://stackoverflow.com/a/526751/5051731) – YetAnotherBot Apr 03 '19 at 01:06
  • 1
    *"I bet it's O(logN) or O(√N), where N is arr.length"* - How much? Seriously dude there is no need to guess. You can work out the number of iterations performed by analyzing the code and doing some simple (high-school level) algebra to work out a precise formula. (Try it for yourself. It is a simple exercise ... and I imagine that's what your teacher wants you to do.) – Stephen C Apr 03 '19 at 01:12
  • Every constant value has to be ignored on Big O. (n^2)/2 can be 1/2 * n^2. 1/2 must be ignored. – kangtaku Apr 03 '19 at 02:18

1 Answers1

3

I think your routine prints something like this:

arr[0] arr[1] arr[2] ... arr[n]
arr[1] arr[2] arr[3] ... arr[n]
...
arr[n]

If the calculation for each step is the printing, then I would say the complexity is O(n^2). Because the number of all the prints is (length+1)*length/2.

Allan
  • 12,117
  • 3
  • 27
  • 51
Cauchy
  • 46
  • 1