f(x) = 4x+5 g(x) = xWe found that the rule above holds for c = 1/5 and n0 = 5. Look at a few values:
|x||f(x) = 4x + 5||g(x) = x||1/5*f(x)|
|1||9||1||9/5 = 1 4/5|
|3||17||3||17/5 = 5 2/5|
|9||41||9||41/5 = 8 1/5|
Notice that f(x) > g(x) everywhere. However, we see that 1/5 f(x) <= g(x) for x >= 5. (The table above does not prove this, but it's easy to do algebraically.) Thus for our f and g it is true that f(x) = O(g(x)) and for proof we need only offer c = 1/5 and n0 = 5.
f(x) = 4x2+5 g(x) = xWe are looking for c and n0 such that for all x >= n0, |c*(4x2 + 5)| <= |x|. Clearly we will need c < 1, as before. Let's try 1/100:
|x||f(x) = 4x2 + 5||g(x) = x||1/100*f(x)|
It turns out that no matter what value we choose for c, we can choose x such that c*f(x) > g(x) (this can be shown algebraically as well).
f(x) = 3n2 + 5n + 2 g(x) = n2
f(x) = n/3 - 4 g(x) = n
f(x) = 5log2(n) g(x) = n
f(x) = n2 g(x) = 3n2 + 5n + 2