CODEWITHSUNDEEP
javasortingcomplexity-theoryinsertion-sort
mbsingh
mbsingh

Reputation: 489

Can InsertionSort complexity be brought down to O(nlogn)?

I was wondering if by using BinarySearch & ArrayLists in java the complexity of InsertionSOrt can be brought down to O(nlogn) from O(n2).

Upvotes: 1

Views: 142

Answers (2)

TheLostMind
TheLostMind

Reputation: 36304

The complexity for Insertion Sort is :

  1. Iterate through all the remaining elements which are to be sorted. (O(n) for n elements)

  2. a. if the next element (say at position k) is greater than the element at pos k-1, then do nothing (checking is O(1) ). i.e, O(n * 1) is best case where already all elements are sorted.

    b. if the element at pos k is smaller than that at k-1, then move the element left until it is greater than the element to its left or there are no elements left to compare. . So O(n*n)

Upvotes: 0

Kakarot
Kakarot

Reputation: 4252

There are 2 things that contribute to O(n2) complexity in insertion sort :

1) Searching appropriate position for the elements to be replaced - which is O(n) per iteration. It can be reduced to O(log n) using binary search.

2) Once the correct position is found then shifting the elements greater than (or smaller than) the element to the right. In the worst case you will insert an element to the front of the list and this would require shifting all remaining elements in the sorted list to the right - Worst case is O(n) per iteration.

So total complexity using Binary Search & ArrayList would be : 

O(n * n + n * log n)

Upvotes: 2

Related Questions