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.
No comments:
Post a Comment