CODEWITHSUNDEEP
javaarraysalgorithmtime-complexitycomplexity-theory
Pasha
Pasha

Reputation: 1912

What is the complexity for such loop?

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)

Upvotes: 0

Views: 56

Answers (1)

Cauchy
Cauchy

Reputation: 46

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.

Upvotes: 3

Related Questions