Running Time Analysis (Week of Nov. 4th)

This week, we learned more about running time analysis, specifically analyzing three different sorting methods. Again, since I do not have a solid background in computer programming, I only knew the concept behind bubble sort. I really appreciate that Professor Heap used cups with different height as visualizer for how each sorting method work. I am pretty sure if I were to look at the code alone; it would take me hours to understand the idea of each sorting method and how it works. The result from the race among the different sorts, including the count sort and the python built-in sort, is also really interesting. For instance, even though both quick sort and merge sort are O(n log n), one still out speed another by a constant.

Speaking of which, I have trouble understand Big-Oh Analysis. When going through the 3 sorting methods in class, it took me a while to understand why each sort corresponds to each function. Selection sort is O(n^2) because during the i^th iteration, the program has to run through (n – i) item in the list. So adding all iteration, selection sort would take n + (n – 1) + (n – 2) + ……. + 2 + 1 number of steps. By Gauss formula, the amount of steps taken is n(n+1)(0.5). Thus selection sort is O(n^2). Similarly, merge sort is O(n log n) because the merge_sort function split the list into two smaller list (ie. It is O(log n)), and the merge function has to go through each item in list 1 and list 2, in which there are n items in list 1 list 2 combined (ie. It is O(n)). Combining the two functions, we will have O(n log n). However, quick sort is the one that I have the most problem. I understand the “log n” part, because quick sort uses the divide and conquer method. Nevertheless, I do not understand where the “n” comes from. I should probably read the background readings again and see if there is any explanation. If I still do not understand, I will probably do some research through Google, and hopefully there will be an explanation on why quick sort is O(n log n).