Comparsion between insertion sort and quick sort

Comment:

It will be good to know the details about the running time estimates of n and n log n for insertion sort and quicksort, respectively.

Follow-up:

Let’s take a look at insertion sort first. We know that insertion sort works by taking each item (e.g., a card) and then compare it with each of the remaining items on the list so as to find a right  position. After the first item is done, we repeat the process for the second item.

Now, suppose we have n items in total, then we need to repeat the above process n times. The next question is: how many comparisons are needed for each item? It is not difficult to see that for the first item, we need to do n – 1 comparisons. For the second item, we need to do n – 2 comparisons. You can go on with this argument until the last item. Thus, the total number of comparisons is:

So, for very large n , we can approximate by (n x n) / 2 . As we are mostly interested in the “order of 2 magnitude”, we can further approximate this by just (n x n).

For quicksort, the mathematical derivation requires solving a “recurrence equation”. Thus, the
mathematics needed is really beyond the scope of the course here. Yet, to get a rough idea, it is similar to the recursive exponentiation we tackled in Tutorial 1 (problem 2).