How to calculate theoretical running time for a created algorithm?

Question

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?

Answer 1

Your first for loop always runs for n iterations and is therefore O(n).

Your last for loop always runs for n iterations and is therefore O(n).

Your middle for loop (inside the while loop) always runs for n - 1 iterations and is therefore O(n).

Now, how many iterations will while loop execute? It appears to be variable, but let's take a closer look at the inner for loop:

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

So, on the first pass through this for loop, i == 0. The if statement ensures that a[1] ≥ a[0] + 1, by setting a[1] = a[0] + 1 if necessary.

On the second pass, i == 1. The if statement ensures that a[2] ≥ a[1] + 1, by setting a[2] if necessary.

On the third pass, i == 2. The if statement ensures that a[3] ≥ a[2] + 1, by setting a[3] if necessary.

Notice that on every pass, the loop can set a[i+1], but no earlier elements. Thus each pass through the inner for loop can never undo the work of a previous pass.

When this inner for loop stops executing, a[i+1] ≥ a[i] + 1 for all i.

The while loop is guaranteed to run at least once. If the inner for loop makes any changes to the array, it sets flag, making the while loop execute a second time. On the second pass through the while loop, the array is already fully groomed, so flag will remain False.

Therefore the while loop executes at most two iterations, so it is O(2n) (the n comes from the O(n) complexity of the inner for loop). And you probably know that O(2n) == O(n).

All the outer loops in your getD function are O(n), so your function is itself O(n).

By the way, you can initialize corrections like this in Python:

corrections = [0] * len(a)