Thursday, November 13, 2014

Under-estimating and Over-estimating

We have been covering big-oh notation over the past couple of weeks, and I feel that I'm starting to finally understand the basic concepts behind it. Progress? Maybe?

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