Week 9: Big-Oh of polynomials, non-polynomials, limits

exercises of big-Oh proofs
 To prove polynomials: it’s all about picking c and B
   ➔ tip 1: c should probably be larger the
   constant factor of the highest-order term
   ➔ tip 2: see what happens when n = 1
   ➔ upper-bound the left
   side by overestimating
   ➔ lower-bound the right
   side by underestimating
   ➔ choose a c that connects
   the two bounds
To disprove, we prove the negation is true!
summary
➔ the ways we talked about of picking c and
B, the main point of them is that we know
how to show the bounding relation when
picking in these ways.
➔ these are not the only ways, you can be
more flexible when you are more familiar
with these types of proofs.
➔ In general, larger c or larger B don’t hurt

 prove big-Oh using limit techniques
to prove non polynomials we use limits - limit = infinity defined by
for all c in positive real number, there exist n' in natural number, for all natural number n bigger than n', the limit > c.
we take the limit of the f(n)/g(n) when evaluating f(n) in O(g(n)) for example, use limit rule above to show fn>cgn (fn/gn > c)
use L'Hopital's rule
lim fn/gn = f'n/g'n