CODEWITHSUNDEEP
sortingtime-complexityinsertion-sort
Drake Drinnon
Drake Drinnon

Reputation: 51

Time Complexity of Insertion Sort

Could anyone explain why insertion sort has a time complexity of Θ(n²)?

I'm fairly certain that I understand time complexity as a concept, but I don't really understand how to apply it to this sorting algorithm. Should I just look to mathematical proofs to find this answer?

Upvotes: 4

Views: 28341

Answers (3)

Akshay
Akshay

Reputation: 247

Worst case time complexity of Insertion Sort algorithm is O(n^2). Worst case of insertion sort comes when elements in the array already stored in decreasing order and you want to sort the array in increasing order.

Suppose you have an array 

Step 1 => | 4 | 3 | 2 | 1 | No. of comparisons = 1  |  No. of movements = 1 
Step 2 => | 3 | 4 | 2 | 1 | No. of comparisons = 2  |  No. of movements = 2
Step 3 => | 2 | 3 | 4 | 1 | No. of comparisons = 3  |  No. of movements = 3
Step 4 => | 1 | 2 | 3 | 4 | No. of comparisons = 4  |  No. of movements = 4

T(n) = 2 + 4 + 6 + 8 + ---------- + 2(n-1)

T(n) = 2 * ( 1 + 2 + 3 + 4 + -------- + (n-1))

T(n) = 2 * (n(n-1))/2

T(n) = O(n^2)

Upvotes: 1

vladich
vladich

Reputation: 608

It only applies to arrays/lists - i.e. structures with O(n) time for insertions/deletions. It can be different for other data structures. For example, for skiplists it will be O(n * log(n)), because binary search is possible in O(log(n)) in skiplist, but insert/delete will be constant.

Upvotes: 1

Gene
Gene

Reputation: 47020

On average each insertion must traverse half the currently sorted list while making one comparison per step. The list grows by one each time.

So starting with a list of length 1 and inserting the first item to get a list of length 2, we have average an traversal of .5 (0 or 1) places. The rest are 1.5 (0, 1, or 2 place), 2.5, 3.5, ... , n-.5 for a list of length n+1.

This is, by simple algebra, 1 + 2 + 3 + ... + n - n*.5 = (n(n+1) - n)/2 = n^2 / 2 = O(n^2)

Note that this is the average case. In the worst case the list must be fully traversed (you are always inserting the next-smallest item into the ascending list). Then you have 1 + 2 + ... n, which is still O(n^2).

In the best case you find the insertion point at the top element with one comparsion, so you have 1+1+1+ (n times) = O(n).

Upvotes: 11

Related Questions