What will be the time complexity of the while loops whose iteration is not predictable?

Question

I have this algorithm written where the while loop can vary from N to 0 depending on the input array, but we cannot give O(N*N) also because if the while loop is executed once for N times, then for the next iteration of x it will be 0 because we are removing it from the dictionary as a result the loop will break in the first iteration. So what is the time complexity of this algorithm in the worst case scenario. If you need to understand the algorithm this is the question for it.[https://www.youtube.com/watch?v=XitBQzqC1O0]

x=[5,4,4,3,3,2]
destroyedBaloons={}
count=0
for i in x:
    if(destroyedBaloons.get(i)):
        destroyedBaloons[i]+=1
    else:
        destroyedBaloons[i]=1
for i in x:
    if(not(destroyedBaloons.get(i))):
        continue
    height =i
    while(height>0):
        if(destroyedBaloons.get(height)):
            destroyedBaloons[height]-=1
            height-=1
        else:
            break
    count+=1    
print(count)```




 

Answer 1

The worst scenario would be the balloons in non-decreasing order, so you would need one arrow for each balloon. First loop would be N iterations, then N - 1, N - 2, etc. so total iterations would be ½(N² + N) or O(N²).