Sorting and Big O

This week, Danny got the chance to talk to us about Sorting Algorithms and their respective run times. Through the use of the playing cards and the diagram that was drawn two weeks ago, Danny helped me gain a better understanding of sorting. When referring to merge sort, it was difficult at first to understand why it was O(n log n). Through Danny's long explanation on the slide, it made it incredibly clear. Danny broke down the sort bit by bit and was able to determine the runtime without error. This made it easier for me to understand how merge sort's run time worked. By splitting the list n times and merging them, we get two separate linear run times of O(n). By increasing the number of sub lists, the equation increases by an exponent. However, when the exponent is the size of log n, the sub lists have a size of one, which means that the runtime must be O(n log n). On other algorithms, like the ones from the test for example, you could tell that one of them just had a normal runtime of O(n) considering that the runtime always depended on a constant of 10.  Lastly, it was a big help to see the hierarchy of upper bounds in the week previous. Danny had drawn out huge circles depicting what each Big O was less than or greater then. Showing the smallest run time to the largest run time helped refresh my memory from CSC165. In conclusion, even though I find Sorting and Big O to still be confusing at times, by dissecting the methods through merge sort, Danny had been able to show us exactly why it had a run time of O(n log n) and explained it simply enough for the class and I to understand.