Watching the free MIT Algorithms course on iTunesU and Im stuck on the first lecture.
Take an insertion sort, its time is really T(n/2) in worst-case (reversed order array/list), but they say that this is theta n squared. I would thought this would be theta n. Im lost how they say this is n squared. Im stuck how they jump to concluding this is n squared, Wikipedia is not helping either. Can someone dumb it down further?
Insertion-sorting an array of 4 elements that starts in reverse order:
4 3 2 1
first, insert the "4" into its proper position in an array of length 1 (i.e. do nothing).
next, insert the "3" into its proper position in an array of length 2:
3 4 2 1
(we had to move the 3 and the 4)
next, insert the "2" into its proper position in an array of length 3:
2 3 4 1
(we had to move the 2, the 3 and the 4)
next, insert the "1"
1 2 3 4
(we had to move the 1, the 2, the 3 and the 4)
We performed n steps, and each step k required moving k elements (or k-1 swaps, depending how you want to look at it). The sum of k from 1 to n is Theta(n^2).
In the case of a simple linked list structure[*], we can move an object into its proper place in O(1), but in general finding the proper place still requires a linear search through the part of the data that's already sorted, so it still ends up only O(n^2) for general input. A basic insertion sort for a linked list happens to deal very well with reverse-ordered data, though, because it happens to always find the correct insertion position immediately. So we get n steps of O(1) each for a total O(n) running time for this particular data.
Assuming we still choose the first unsorted element to insert, and that we search forward through the sorted part of the list at each step, then the worst case of insertion sort for a list is already-sorted data, and is Theta(n^2) again.
[*] meaning, nothing fancy like a skip list.
From wikipedia:
The worst case input is an array sorted in reverse order. In this case every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element. For this case insertion sort has a quadratic running time (i.e., O(n2)).
First loop is iterating on the array/list to sort, inner loop iterates on the partially sorted array/list. If it's already sorted you can see that you iterate all the way to the end of the sorted container every time.
Here's more explanation in pseudo:
for element in unsorted_container
for current_element in sorted_container
if element < current_element -> Will never happen since sorted in reverse order.
InsertBefore(element, current_element)
if element not inserted
InsertAtEnd(element) <- Will always execute this part since it will always insert at end.
