The only difference between big-oh and big-omega is that it's "f(x) <= cg(x)" in big-oh and it's " f(x) >= cg(x)" for big-omega. The strategy to prove is also pretty much alike. The big-theta is the combination of the two properties above. I think this section is relatively easy in the whole course.
However, there's still a tough problem in this easy section, that is the notorious problem 5 in assignment 3. It asked us to prove or disprove that "for f, g(x) in functions(N->R>=0), f in O(g) or f in omega(g)." This assumption looked so reasonable at first that me and my partner both thought we'd have to prove it and spent many hours but came up with nothing. Finally we found that f(n): n if n odd, n^3 if n even, g(n): n^2 can falsify this argument because f neither in O(g) nor in omega(g).
Although this argument is not correct, I think if I add more precondition I can make it right. I guess that if I add f, g(x) are both monotonic and nonzero then this assumption will be right.(just a guess). I think it's really a good problem and I learned that we can never say anything for sure until we proved it, even if it looks pretty reasonable!
No comments:
Post a Comment