Week 7 and 8 - Big OOOOOOOOOOO

For the last two weeks we have been talking about a brand new topic - algorithm analysis and big O. What do we want from these complicated stuff? We want to see how our program runtime depend on our input sizes, what if the input size grows really large, how would our program run time fare up? 

Ideally, we want our program to run as fast with a small input as with a huge input, and to eliminate the cases that it grows exponentially, therefore, we must come up with a way to measure our program runtime. It is called big O.
Because we can generate an approximated runtime formula from our code, we can calculate the level of growth it has, for example x^2 + 100x +5, we can try to think what would happen if the input size x is really huge, almost if it is approaching infinity. If we set lim x->inf, the 100x and 5 hardly matters compared to x^2, they matter so little that in high school calculus we simply eliminates them. This is also how we handles it here, the function we had grows at a level of x^2, it would not grow much faster or slower compared to it, so we dubbed it O(x^2) and Omega(x^2), and if a function belong to both O and Omega, we call it theta.

A precise definition of big O is 

that if we can choose a multiplier and a breaking point so that a function f upper bounds our function g after that point, our function grows no faster than f, It is big-Oed by f.
for Omega, we just have to change the <= sign to >= sign.
When we estimate the runtime of a function, we do it by evaluating the runtime of the inner loop first,  then come out one by one, we can slightly overestimate when we are trying to find big O, because if the over-estimated runtime doesn't grow faster than a function, our original sure doesn't. The opposite goes for Omega, we underestimate the runtime so if our underestimation grows no slower than f, our original which grows >= underestimation definitely grows no slower than f.