The classes for CSC148 is over. Over the course of past a month and a half, we've been introduced to the concept of complexity in algorithms. Just a recap, a complexity of an algorithm is how the algorithm's run time as the size of the parameter gets large. This type of scaling is more apparent in the types of algorithms we have been dealing with, which is sorting. The reason for this is because the number of elements in a list takes on integer values so we can clearly see what happens to the number of steps as we increase the size of the list by one. The most common big- oh complexities are logarithmic, constant, linear, quadratic, cubic and so on. In the labs, we examined various sorts graphing the running-time for different scenarios of the list such as sorted, sorted backwards and unsorted. The sort can basically be divided into two kinds, the ones with average complexity of O(n^2) and the ones with average complexity of O(nlogn). Sorts such as insertions sort, selection sort, and bubble sort are all O(n^2) because they require the computer to find individual values whether it be finding the smallest value or switch out the largest value, they all require a portion of the list to be repeatedly looked after after each iteration. And the difference within these O(n^2) sorts depends on the the length of the portion they had to look at. For example bubble sort despite how the last numbers are sorted, it still goes through the switching algorithmns with the numbers staying in their same place, while for insertion sort it only looks at the unsorted portion and if the list is already unsorted then it would just compare a term with only its previous term, making it O(n) in the best scenario. And for the merge sort and quick sort, they are O(nlogn) because it partitions the list into two parts either using a pivot or just in halves and recursively repeat the process until we reach one element and arrange them in order. It's logn because it dpends on how many times n can be divided into two and n because the single element needs to be compared with other elements so it can be arranged. Furthermore, going through the minor tweeks such as creating a global variable for len(L) or making sure that bubble sort doesn't try to swap the sorted end has increased dramatically the run time of the sorts. To conclude, work with sorts in the labs has given me a better understand of complexity and has made me more aware as to how minor details can have great effect on the running time.
This was a good semester.
