Week 8

This week, we started looking at algorithm analysis and asymptotic notation. We looked at big O, which provides the upper bound for the growth rate of a function, as well as big Ω, which provides the lower bound for the growth rate of a function. It was interesting to learn that in terms of complexity, constants are ignored.

A function with a constant time complexity that doesn't depend on the size of the input is O(1). One example if this is the average time complexity for search, insertion, and deletion for a hash table data structure. Hash tables are used because they are very efficient in that keys are mapped to a value so that only one key has to be looked up. This is the reason why they are used very commonly. We can compare this to the linked list data structure, which takes O(n) on average for searching, since it has to go through each item sequentially until it finds the item it is looking for.

Another interesting thing I learned this week was the formula for summing up the integers from 1 to n. The story of Gauss coming up with this solution when he was young also makes this easier to come up with.

This is sort of unrelated, but I came across a very interesting video of the visualization and "audibilization" of 15 sorting algorithms. I think it is a great introduction to sorting algorithms you may not have seen before. Perhaps the most beautiful is the bogo sort.

The second assignment was harder than expected but I eventually figured them out and next week is the second midterm but I am not as worried as the first midterm since I did well on the first one but hopefully this one goes just as well!

An interesting SLOG post I found is here: http://csc165.peet.io/big-o-notation/ (this blog also has a very nice, responsive design). This student writes about the penny puzzle that I previously also wrote about and gives an analysis of the algorithm in big O notation. I think this a very good post because it brings up the importance of run-time when writing programs. When I usually write a program, there is very little thought that goes into thinking about the program's running time but this is something that can have a large effect on your program depending on size of your inputs.