I need some help analyzing my algorithm to determine its theoretical running time. I think I understand how to analyze most of it. I'm not sure how to analyze the **while loop** that contains a **for loop**. Ill provide my algorithm, followed by what I think/know.

## My Algorithm:

```
def getD(a):
corrections = [] #list for correction values
comparisons = 0 #comparison counter
#initialize corrections list with all 0's
for i in range(0,len(a)):
corrections.append(0)
flag = True #loop control
while(flag):
flag = False
#loop through list
for i in range(0,len(a)-1):
current = a[i] #current element value
nxt = a[i+1] #next element value
dif = nxt - (current + 1)
#correct the nxt item.. i+1. comparisons++
if(dif < 0):
comparisons += 1
corrections[i+1] -= dif
a[i+1] -= dif
flag = True
d = int((max(corrections)+1)/2)
#balance the corrections
for i in range(len(a)):
corrections[i] -= d
print(d)
print("Number of comparisons:",comparisons)
```

## My progressing analysis:

n = length of the input list (a)

The dominating operations are the 3 for loops and the while loop.

The first **for loop** iterates n times.. so it has a running time of **n.**

The last for loop also iterates n times.. applying the corrections to each element, so it also has a running time of **n.**

For the 2 **for loops** above.. I think the combined running time would be 2n? But there's more to add for the entire algorithm running time.

Here's where I start to struggle:

The dominating operations left (I believe) is the **while** loop with the **for** loop inside.The **for** loop will run **at most** n-1 times. But if dif < 0, it runs the for loop starting with i=0 again.

I'm not sure what the run time for this part would be or the algorithm as a whole. How do I calculate the while with the last for loop in it? How would I combine them all together?