In week 3's lecture, David talked about the concept of runtime where the worst possible scenario for say insertion sort is O(n squared) and the best case scenario would be omega(n). I dont understand how the n counter works. Does it increase by one every time you go to the next element in an array or does it increase by one only if you do an action(eg a swap) on an element? For the best case scenario to be omega(n), it seems like the n counter has to increase by one every time you go to the next element assuming no swaps are required yet in the worst case scenario, you ignore the scanning or moving to the next element and simply increase the counter when you need to do a swap. Sorry if my question is too long-winded and seemingly confusing. Thank you!
1 Answer
n here is the number of elements in the array.
One implementation of insertion sort is going through the elements from left to right, and swapping them with their left neighbour as long as that one is greater than the newly inserted element. Other implementations may avoid about half of the read/write operations by doing only one half of the swap (and remembering the one element travelling backwards until it has reached its destination), but all have the same complexity.
So for an array sorted in the wrong direction (worst case for insertion sort), that would mean n*(n-1)/2 comparison and n*(n-1)/2 swap operations, leaving only the highest power (as that's what dominates for large n) and dropping the 1/2 factor, you'll end up at n^2.
For an array sorted in the right direction, you'd do n-1 comparisons and no swaps at all, again only the highest power, n, is used.
