Example 1

Example 1

Show that " f(n) is O(n^2)" when "f(n) = 5 * n(n + 100)".

To do this, we have to show that f(n) ≤ C * (n^2) (or equivalently, 5 * n(n + 100) ≤ C * (n^2) - as per the definition) when n is bigger than the value n0 (which we will determine).

We might do this by first arbitrarily picking a value of C or n0. If, for example we choose c = 10, then the equation becomes

5 * n(n + 100) ≤ 10 * (n^2) simplified, giving n(n + 100) ≤ 2 * (n^2)

Now, we just have find a value of n0, whereby when n0 ≤ n ' the inequality becomes true.

In this case, if we solve the inequality for n, n ≤ 0 or n ≥ 100 . So, when n ≥ 100 , the inequality is true, and we can give n0 ANY value that is bigger than 100.

Since it is possible to find a set of constant values for C and n0, such that f(n) ≤ C * g(n) (when n ≥ n0 ), we show that f(n) is O(n^2) .