This week,we shifted our focuses gradually from Big O to Big Omega. The proofs is kind of similar to that of Big O. And the main idea (and the hard part) of the proof is to find a magic breakpoint B and simplify the function without changing the highest degree, since the lower degrees are negligible compared to highest degrees and thus can be ignored.
Also, prof taught us a way of determining if the functions satisfy the Big O or Big Omega by calculating the limit of the division of two functions as N goes to infinity. The limit will tell us the answer because it tells us the behavior of two functions near infinity and thus we can speculate the validity of f <= cg or f >= cg.
No comments:
Post a Comment