Week 9: One big oh!

This week we did work on Binary Search Trees (BSTs) and in particular looked at deletion of data from BSTs during lecture. We also started learning about algorithm performance and analyzing the running time of an algorithm in terms of the size of the input n. We looked at the worst case scenarios of sorting algorithms and found that binary search is almost always more efficient than linear search which is pretty cool.

The idea of the big-oh notation is to give an upper bound on the worst case running time of an algorithm. For example, O(n) means that the algorithm's performance is directly proportional to the size of the input passed to it. Similarly, O(n²) means that the algorithm's performance is proportional to the size of the input squared. Since the big-oh is an upper bound, we can see that we can write things like O(n) ⊆ O(n²). That is, the run time of algorithms that are proportional to the size of the input will most certainly be less than (or bounded above by) the run time of algorithms that are proportional to square of the size of the input. In theory, the idea of an upper bound was easy for me to grasp but understanding it on an example is definitely something I have to spend some time on.

A2 part deux is due this week, so time to get to finishing it. Until next time, adieu!