Estimate computational cost of a sorting algorithm

Question

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.

trincot · Accepted Answer · 2022-10-17 19:49:33Z

1

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²)

answered Oct 17, 2022 at 19:49

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

user1196549 · Accepted Answer · 2022-10-17 21:10:43Z

0

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.)

answered Oct 17, 2022 at 21:10

user1196549

Collectives™ on Stack Overflow

Estimate computational cost of a sorting algorithm

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related