Example 3

Example 3

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

To show that f(n) is Θ(n^2), we have to show that f(n) = O(g(n)) and f(n) = Ω(g(n)).

We have already shown that f(n) = O(g(n)) in example 1, so now we'll focus on the second part.

Firstly, notice that f(n) = Ω(g(n)) is the same as g(n) = O(f(n)). We will show that the second statement is true.

( n^2 ) ≤ C * ( n ( n + 100 ) )

If we choose C to be 2, then: ( n^2 ) ≤ 2 * ( n^2 + 100*n )

Rearranging gives: 0 ≤ n^2 + 100*n

So the solutions to the equations are n ≥ 0 and n ≥ 100.

"g(n) ≤ C * f(n)" is true when C = 2 and n0 ≥ 0.

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