CSC165 Week 10

We finished about the proof of big-Oh and big-Omega. Here is a short summary of chapter 4 about those proofs:

1. Definition of big-Oh, big-Omega.

2. big-Oh proofs for polynomials(standard procedure with over/underestimates)

3.big-Oh proofs for non-polynomials (need to use limits and L’Hopital’s rule)

4. proofs for general big-Oh statements(pick B and c based on known B’s and c’s)

 We also started chapter 5 this week. It's about the computability. For anything that in order to be computable for computers, that function can only go through by finite times. It can not be infinite. If the function is supposed have infinite loop inside, the result will never be computed. 

CSC165 Week9

For this week, we started the proof of 'big-Oh' of polynomials, non-polynomials and limits. The proof structure is the same as we used before but with much more details in it.  It involves a lot of application of math which means it is not that easy to see how to do it, since some math stuff can not be used directly.

For those function in form of polynomial the proof is kind of easy. Basically is find the upper-bound of the left side by overestimating and find the lower-bound of the right side by underestimation and then choose a c that connects the two bounds. For disproving, it just the same as what we've done before, prove the negation of the original statement.

For non-polynomials we need to use limits to prove the big-Oh. The steps are follow:
1. Prove the limit of the function is infinite as n goes to infinite. This step may involves using the L'Hopital's rule.
2. Translate the limit into its definition.
3. Relate it to the definition of big-Oh.