Week 12- Review of Week 11

In week 11, we learned about Big-Oh. This was a fairly easy concept for me because we spent a fair amount of time on it in CSC165 that I took last semester.

The concept of Big-Oh states that a function is in BigOh(fn) if the function grows no faster than f(n) after a certain point. Or alternatively, f(n) is the upper bound of the function.

Notation wise we can use the following example to illustrate BigOh
O(f) = {g : N → R >0 | ∃c ∈ R + , ∃B ∈ N, ∀n ∈ N, n > B⇒g(n)<= cf(n)
This notation basically explains what I said earlier, which is that then) function g(n) will not grow faster than a constant c times f(n) after the point B.


The fundamental purpose of Big-Oh is to test the running time of a function. If the running time of the function is slower or equal to Big-Oh, we say the function is in Big-Oh, else we say the function is not in Big-Oh.For instance, the function 3x^2 would be in BigOh(x^2) but would not be in BigOh(x).

In this lecture we discussed mainly with linear or quadratic running time. We also touched upon on some ways to solve running time question. For instance, when we solve for while loop running time, we times the running time of the inner loop with the running time of the body loop(of the while loop） to produce a result.

In terms of the application of Big-Oh in reality, I am still very unsure. I suppose it will be used as a way to test the efficiency of a function. For instance, it would likely choose the function that runs with the least amount of running time to increase efficiency.