f(x) = 4x+5 g(x) = xWe found that the rule above holds for c = 1/5 and n_{0} = 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 |
5 | 25 | 5 | 5 |
7 | 33 | 7 | 33/5=6 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 n_{0} = 5.
f(x) = 4x^{2}+5 g(x) = xWe are looking for c and n_{0} such that for all x >= n_{0}, |c*(4x^{2} + 5)| <= |x|. Clearly we will need c < 1, as before. Let's try 1/100:
x | f(x) = 4x^{2} + 5 | g(x) = x | 1/100*f(x) |
1 | 9 | 1 | 9/100 |
3 | 41 | 3 | 41/100 |
5 | 105 | 5 | 105/100 |
7 | 201 | 7 | 201/100 |
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) = 3n^{2} + 5n + 2 g(x) = n^{2}
f(x) = n/3 - 4 g(x) = n
f(x) = 5log_{2}(n) g(x) = n
f(x) = n^{2} g(x) = 3n^{2} + 5n + 2