Big-O Notation

We covered big-O notation in class over the past couple of weeks. There are a few things which struck me as interesting. Each function belongs to a set of functions with the same run-time performance. For example, a linear search will belong to the set of functions with O(n) performance whereas a binary search will have O(log n) performance. But technically, big-O is an upper bound on an algorithm's performance. In other words, all of these sets fit into a hierarchy. So O(log n) is a subset of functions with O(n) performance (since functions with O(log n) performance cannot possibly do worse than an O(n) function). Similarly, O(n) is a subset of functions with O(n*log n) performance. So technically, a binary search algorithm fits under O(log n), but it also fits under O(n) and O(n*log n). This is what I found somewhat strange. Can I claim every algorithm given on the upcoming midterm is O(n!) and get full marks? This seems absurd.

To address this, I would assume an algorithm is classified by its simplest performance. In other words, we say linear search is O(n) and not O(n!). I don't think this was directly mentioned in class, but it seems to be a reasonable assumption to make. This was later verified in my CSC165 lecture. Hopefully the material covered in my CSC165 class will help with big-O questions on the midterm, and maybe the material covered in CSC148 will also help with my CSC165 class (awesome timing)!

Anyway, good luck on your upcoming midterms!