Hi everyone, this slog (which is the last slog ever!) will be about sorting and efficiency.
In the past few weeks in class, we learned about a way to express the efficiency of algorithms based on their runtime, using something called Big-O notation. In simple terms, if we say a function is "Big-O of n2" that means that the function n2 is an upper bound for the runtime of our function on input of size n. This notation simplifies things considerably, as it enables us to only consider the runtime of a function when the size of the input (for example, a list) is large. As well, it allows us to group functions with similar runtimes together. For example, say that the runtime of a certain function is n2 + 14n + 63, and the runtime of another is 3n2. When n (the size of the input) becomes very large, the lower terms (14n + 63) will be irrelevant compared to the highest order term. Thus we can ignore them for when the list is really large. We also know that since these runtimes will only differ by a factor of 3 when n is very large, their runtimes will be similar enough that we want to be able to group them together. Thus using Big-O notation, we say both functions are O(n2). This simplification will allow us to classify functions by their general behaviour, and give us a better understanding of how efficient they are.
In CSC108, the three sorting algorithms we looked at (bubble sort, selection sort, insertion sort) were all O(n2). In 148, since we are able to divide the list in half and sort it recursively, the runtime of quick sort (in the average case) and merge sort is O(nlogn). This is because we are dividing the list in half everytime (which is logn steps) and at each step, we make n comparisons. O(nlogn) is much quicker than O(n2) for large values of n. For example, if we have a list of 10,000 elements, the runtime of quick sort will be about 13,000 compared to selection sort, which will be 100 million (relatively speaking). This shows the efficiency of quick sort, and demonstrates the usefulness of Big-O in knowing how long a certain algorithm will take to execute.
Good luck on the final exam everyone!
