CODEWITHSUNDEEP
algorithmsortingbig-oinsertion-sort
FrostyStraw
FrostyStraw

Reputation: 1656

Can someone explain to me why the worst case for insertion sort is O(n^2)?

Can somebody do like a step by step explanation of how we get O(N^2) when finding the worst-case analysis of insertion sort? I'm currently reading an explanation for it from the Cormen Intro to Algorithms book, but the explanation is sort of confusing.

Upvotes: 0

Views: 29315

Answers (3)

Jimmy
Jimmy

Reputation: 1051

Let the pseudocode:

for i = 1 to length(A)
    x = A[i]
    j = i - 1
    while j >= 0 and A[j] > x
        A[j+1] = A[j]
        j = j - 1
    end while
    A[j+1] = x
 end for

Complexity of Insertion Sort

Insertion sort runs in O(n) time in its best case and runs in O(n^2) in its worst and average cases.

Best Case Analysis:

Insertion sort performs two operations: it scans through the list, comparing each pair of elements, and it swaps elements if they are out of order. Each operation contributes to the running time of the algorithm.

If the input array is already in sorted order, insertion sort compares O(n) elements and performs no swaps (in the pseudocode above, the inner loop is never triggered). Therefore, in the best case, insertion sort runs in O(n) time.

Worst and Average Case Analysis:

The worst case for insertion sort will occur when the input list is in decreasing order. To insert the last element, we need at most n-1 comparisons and at most n-1 swaps. To insert the second to last element, we need at most n-2 comparisons and at most n-2 swaps, and so on.. The number of operations needed to perform insertion sort is therefore: 2 × (1+2+⋯+n−2+n−1).

To calculate the recurrence relation for this algorithm, use the following:

2(n−1)(n−1+1)/2 =n(n−1)

Use the master theorem to solve this recurrence for the running time. As expected, the algorithm's complexity is O(n^2)

When analysing algorithms- the average case often has the same complexity as the worst case. So insertion sort, on average, takes O(n^2) time.

Insertion sort has a fast best-case running time and is a good sorting algorithm to use if the input list is already mostly sorted. For larger or more unordered lists, an algorithm with a faster worst and average-case running time, such as merge sort, would be a better choice.

Insertion sort is a stable sort with a space complexity of O(1).

Upvotes: 2

Vikram Bhat
Vikram Bhat

Reputation: 6246

Insertion sort works fast on nearly sorted input so to do worst case analysis you can use the array with numbers in descending order. As if numbers are in descending order then you need to shift (i-1) numbers in ith iteration hence T(n) = sum(i-1) for i in range(1,n) = n*(n-1)/2 = O(n^2)

Upvotes: 1

Cody Piersall
Cody Piersall

Reputation: 8547

In short, the worst case is when your list is in the exact opposite order you need. In that case:

  • For the first item, you make 0 comparisons, of course.
  • For the second item, you compare it to the first item and find that they are not in the right position; you've made 1 comparison.
  • For the third, you compare it with both, and find that the third has to go to the top. You've made 2 comparisons.
  • This goes on; for every following value, you make one more comparison.
  • Finally, for the nth item, you make n - 1 comparisons.

If you add up the number of comparisons you make for the worst case, you'll see that it is 0 + 1 + 2 + ... + n-1, which is equal to (n^2 - n) / 2 comparisons for the worst case, which is O(n^2). (The part that determines the complexity is when we consider large n, in which case the n^2 term dominates)

Upvotes: 15

Related Questions