Q: big O of nested while loop inside for loop

Question

I implement counting occurrence of integer from 1 to n in n-length list. The condition is no additional data structures allow. Manipulate only the original list. Print out the integer and its counts
For example:

org_arr  = [3, 4, 3, 1]
count_int(org_arr )
for i, item in enumerate(org_arr , 1):
    print(i, '->', abs(item))

output:

1 -> 1
2 -> 0
3 -> 2
4 -> 1

Below is my implementation of count_int()

def count_int(arr):
    for i, check_index in enumerate(arr):
        if check_index > 0:
            arr[i] = 0
            while True:
                next_item = arr[check_index-1]
                if next_item < 0:
                    arr[check_index-1] -= 1
                    break
                elif next_item > 0:                     
                    arr[check_index-1] = -1
                    check_index = next_item
                else:
                    arr[check_index-1] = -1
                    break 

the count_int() uses negative counting and index = k - 1 for integer k (as specified 1 <= k <= n) to accomplish the goal. After running, original array org_arr is [-1, 0, -2, -1]

My question is on the big O of this function. Is it O(n) or O(n^2)?

In the worst case, for-loop of org_arr[0] requires n-1 loops of while-loop to set value of org_arr[1] to org_arr[n-1] to negative counters. After that, the while-loop will never be called. Therefore, it is (n-1) while-loops + (n-1) for-loops. It's gonna be 2(n-1). So, it is O(n), but my friend say it is O(n^2) because there is a nested while-loop inside for-loop.

Answer 1

Your analysis is correct. In many cases, a nested loop would result in O(n^2) performance, but in this case the same index cannot be positive twice in the while loop. This means that the total runtime of the while loop over all iterations will be at most n times a constant plus n times another constant, which is O(n) (since it can inspect up to n elements in one loop, but after that will return in constant time if the same element is hit again). Of course it cannot run faster than O(n), since the for loop touches each element once.