More Big Oh

Its time to get a bit more complicated with Big Oh.  In other words, lets actually try to apply the working definition of Big-Oh to proofs.  As a reminder here is the formal definition of Big-Oh as introduced in class.  That is,

1. A function f(n) is O(g(n)) of a function g(n) if there exists  A∈ and B∈ + such that if n>B then f(n) ≤ Ag(n). This is what it means for a function f(n) to be in O(g(n)).

Now, I'll be the first to admit that the course has gotten considerably more challenging since the start.  Let me elaborate on this point.  Big-Oh proofs, as discussed in lecture, are rather simple.  The approach is systematic for most problems of this nature.  For instance, trying to show that 3n^2 + 2n + 5 ∈ O(n^2) is rather simple, similarly to the problem 7n^6 - 5n^4 + 2n^3  ∈ O(6n^8 - 4n^5 + 2n).  Now the disproving aspect can be a bit more challenging depending on the mathematical expressions involved.  I personally found difficulty in attempting to solve the Week 10 Tutorial problem 2.  The problem asked to prove 6n^5 - 4n^3 + 2n^2 ∉  O(5n^4 - 3n^2 + 1).  I was stuck on this problem for some time, as I could not find a suitable value of n to choose.  However, the Big-Oh proofs involving non polynomials gets even worse.  I understand L'Hopitals Rule, and the process by which we can determine which function grows faster.  The part that confuses me is the definition of the limit involving infinities.  These are areas I need to improve in quickly.  Here are my next steps:

1. Review lecture notes covering Big-Oh of polynomials, non-polynomials, limits
2. Work through the tutorial problems for week 10 again.
3. Work through some of the extra practice problems linked on the course homepage.
4. Post questions that further confuse me on Piazza.