I had some confusion about big-oh and big-omega, originally I thought in order to disprove big-oh statement , you would have to prove big - omega. which is clearly wrong. Some function can be true in both big-oh and big-omega. it just simply means that the function is bounded above and below. I just realize from the assignment 3 question 1 and 2. I think proving polynomial statements are pretty easy, We just need to determined the highest-degree term in big-oh / big-omega .
In big-oh , if the highest -degree term is greater or equal , then the statement is true , otherwise disprove it by negating the statement.
In big-omega ,is the opposite. if the highest - degree term is smaller or equal , then the statement is true , otherwise disprove it by negating the statement.
However , I still have trouble understand non-polynomials statement and using limits , L'hopital rule. to prove it.
Yes, exactly. Also if you negate the definition of big-Oh you notice that you don't get the definition of big-omega.
ReplyDeleteIn general, just to be safe, I would suggest that whenever you are asked to disprove a statement, simply negate it and try to prove its negation. There is no chance you can go wrong there.