I think the most important realization was that when given a f(n) >= cg(n), that you should approach the problem by "under-estimating" the right and "over-estimating" the left, and ultimately meeting in the middle. Then, choose a c that makes the right-side an upperbound.
To under-estimate (Right Side)
- remove a positive term
- multiply a negative term
To over-estimate (Left Side)
- remove a negative term
- multiple a positive term
We're trying to simplify the function without changing the highest degree.
Progress has been made, folks.
No comments:
Post a Comment