Week 8: Let's be formal

This week we learned the formal definition of big O.

This means that f(n) is in O(n^2) if and only if after a certain breakpoint B (for all values of n >= B), the graph of f(n) is upper-bounded by the graph of cn^2 (where n^2 is multiplied by a big enough constant factor c). In other words, f(n) eventually grows at the same rate as n^2 at most, if not slower.

Similarly, we can define the lower-bound, when f(n) eventually grows at least as fast as n^2:

and the tight bound, when f(n) grows at the same rate as n^2:

 
Thus, we can say that 7n^2 is in Θ(n^2). From the graph below, we can see that 7n^2 is upper-bounded by 10n^2 and lower-bounded by n^2.

We also calculated the number of steps an algorithm takes depending on the input size n in the worst case scenario, which turned out to be not as difficult as I had imagined. Of course, we were only looking at simple algorithms. I'm curious now as to what we will be learning in CSC236.