In class today, we covered the current Complexity and Computability for Computers.These concepts are essential to Computer Science because the process of writing algorithms is not limited to writing correct syntax. In fact, that is the first step for programmers. Once the programmer understands the syntax for a language, he or she must then research how much money and time an algorithm requires because every additional bit costs a lot for storage. These questions are not covered in introductory programming, but they make the difference between writing a program to count apples to finding the fastest route between points. Although Graph Theory solves this problem, there is plenty of real life applications, from walking between classes in college to how Google Maps gives you the fastest route to your destination. So, how is one algorithm better than the other? Well, one algorithm is considered better if it takes less steps to complete.
In the context of our class, we covered two sorting algorithms: Insertion and Merge. Insertion takes n^2 number of steps to complete while Merge takes n*log2n steps to complete, n being the size of the list. Through these examples, it is clear that Merge sorting is better than Insertion. However, is it the best? Well, not really. At the end of the day though, whatever the best sorting algorithm really is depends on the input (and who you ask). There is an algorithm known as Quicksort which can take less steps than Merge steps. The time complexity of Quicksort is O(n log n) in the best case, O(n log n) in the average case, and O(n^2) in the worst case. Let’s discover how they compare:
Like Merge sort, quick sort works like a recursive procedure (a function that calls itself). The key to understanding this algorithm is to think of it as a pivot. Without going into too much detail, this is how it works: the goal is to rearrange the array such that all all elements less than the pivot are to its left, and all elements greater than the pivot are to its right. Sounds simple, but how to do it will take me pages. Regardless, the important distinction is storage. Why quicksort is better than mergesort ? Quick sort is an in-place sorting algorithm. In-place sorting means no additional storage space is needed to perform sorting. Merge sort requires a temporary array to merge the sorted arrays and hence it is not in-place giving Quick sort the advantage of space. Like I mentioned before, more storage equals more money. So, in terms of price and speed, Quicksort outperforms Merge Sort.
That was a lot of information, so what’s the importance? Well, the problem lies when programmers that are only taught syntax never consider storage cost and processing power. Unless we do something about it, potentially billions of dollars are at stake for storing the large quantities of information from the Digital Age. To further the conservation, here are some additional questions to build upon: can we build faster and cheaper sorting algorithms? If so, how? Is there ethical implications of storing and sorting so much information at a faster rate? How can we assure that all programmers understand the implications of writing code?
