week 9

We have been continuing doing some proves on concepts of big-oh and big-omega notations.

The definition of big-oh notation is f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n. 

The definition of big-omega notation is f(n) = Ω(g(n)) means there are positive constants c and k, such that f(n) ≥ cg(n) ≥ 0 for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.

But the difference between this week and last week is that, we are proving the relationship between two functions, rather than estimating the steps of a program would take.

For example, f(n) = O(g(n)), all we need to prove is f(n) will eventually dominated by g(n)

In this case, we need to prove from a point, (6n^5 - 4n^3 + 2n) ≥(5n^4 - 3n^2 +1)