В чем сложность такого цикла?

Question

Не могли бы вы помочь мне прояснить, в чем сложность следующего фрагмента кода, где я перебираю "не посещаемые" элементы в массиве на каждом шаге?

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]);
    }
}

Могу поспорить, что это O(NlogN) или O(N√N), где N равно arr.length

Я прав?Не могли бы вы объяснить мне, почему?

Я думаю, что это O(NlogN) или O(N√N), потому что на каждом шаге "не посещаемая" часть уменьшается, поэтому она меньше, чем O(N^2), но все же больше, чем O(N)* 1016.*

Answer 1

Я думаю, что ваша рутина печатает что-то вроде этого:

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

Если вычислением для каждого шага является печать, то я бы сказал, что сложность равна O(n^2).Потому что количество всех отпечатков равно (length+1)*length/2.