Week 10

This week we ended the topic about analyzing bounding a sort and linear search. We focused on proving the worst cases (both upper bounds and lower bounds). More importantly, I have finally understood how to analyze (finding steps) of codes during the tutorial section with Jason.

Following picture was an example that we did in tutorial section:

Furthermore, we did some proof exercises:
During the lecture, we were given an example of big Oh. 

In this case, n^2 was the function.
f : N -> R^>=0 : the function that takes in a natural number and return a non-negative real number.
The rest of the function basically told us that n^2 or f(n) was upperbounded by cn^2 (beyond the breaking point B).

Next, we learned to disprove this Big Oh example by negating it then proving it true.
So the negation of n^3 <= c3n^2 to n >= B and n^3 > c3n^2.
We chose a value for n, but before that we have some logical steps to write down.
We broke n^3 down into n times n^2. Since n^3 > c3n^2, then we could comment that n > 3c so n^3 > c3n^2 was true. Now, we introduced ceiling. Ceiling was a symbol that had the opposite meaning of floor. When we used floor, for example, floor 3.249 ( a random number I picked) then we got the answer of 3 because floor meant the largest integer that was less than or equaled to x. On the other hand,  ceiling 3.249 then we got the result of 4 because ceiling meant that we rounded up the number in the first digit by 1. Therefore,  we came up with the result that n >= ceiling 3c + 1 and n > 3c at the same time. Then we got n >= B and n^3 > c3n^2.

In addition, Big Omega was introduced, which we were given with this example.

As you could noticed, this example was very similar to the Big Oh example. There were two differences, first one was that we changed the symbol of Big Oh (O) to the symbol of Big Omega (Ω) and second one was that we changed from ≤ to ≥ between f(n) and c(function - differed in different cases)

Following, we were introduced with a new bound, which it only happened when the functions were bounded above and below by the same function. 

 

In this case, we combined two concepts into 

 

Last,but not least we were introduced how to prove a non-polynomial example.

General procedure of solving: 

1. Prove the limit of using some rules we learned in calculus. For example, L' Hospital Rule 

2. Translate the limit into its definition with c and n' 

 

3. Relate this definition to the definition of Big-Oh.

then we got