Example 2

Example 2

Show whether : f(n) is O(1) when f(n) = n - 3

We know that intuitively that f(n) is NOT O(1), but we'll see if we can show this more formally.

We know that if f(n) is O(1), then n - 3 ≤ C * 1 is also true, for a pair of constants C and n0.

However, whatever large the value we pick for C and n0, the inequality eventually will become untrue as n increases towards infinity.

(If we arrange the equation into n ≤ (C * 1) + 3 we can see that the right side are all constants, and as n approaches infinity, the inequality becomes false.)

Since we cannot find a pair of constants values C and n0, we know that f(n) is not O(1) .