Today, my algorithm teacher gave me a little exercise in introducing computational cost. The code is as follows:

A = [8,7,6,5,4,3,2,1]
for y in range (0, len(A)):
   el = A[y]
   i = y-1
   while i >= 0 and A[i] > el:
      A[i 1] = A[i]
      i = i-1
   A[i 1] = el

Without wasting your time: it is an algorithm that takes an array and reorders it. I have to find out what order is O. Considering that all assignment operations use 1 as a cost, the "heaviest" lines are the for and the while. If the for loop is of the order of O (n) with n = len (A) I can't figure out how to calculate the while. Worst case it runs 28 times, but I can't find a correlation with the length of the array. Can someone help me? Many thanks in advance.

CodePudding user response：

For the given input the condition A[i] > el will always be true when it gets evaluated, as every next value el is less than all preceding values A[i]. So the input really triggers a worst case execution.

Then the number if executions of the inner loop increases with one every time the outer loop makes an iteration:

0
1
2
3
...
n-1

The sum of all these is a triangular number: n(n-1)/2, which is O(n²)

CodePudding user response：

The while loop inserts A[y] (for some y) in the subarray A[0..y-1] before it. As you can verify, when performed on increasing y, this makes A[0..y] sorted. The cost of the while loop is proportional to the distance between y and the insertion point. At best, this distance is always 1 (A[y] already in place); at worst, it is y (A[y] should come first, as on the given input); on average, y/2 for a uniform distribution.

Hence, globally, the sort is at best Θ(n), but at worst and on average Θ(n²). (Sum of integers up to n.)