_{}

Let:

_{}

f and g are two strictly increasing functions (for n >0) and they have no inflexion point (the second order derivative never equals 0 for n>0), which means they have 0, 1 or 2 intersection points. On a plot of the two functions, one can see that they have two intersection points. We don’t need the exact values since n is an integer. From the graph, we conclude that f(n) > g(n) when: 1< n < 23.

From the equivalence relation shown above:

_{} holds when 1< n
< 23.

**1 ^{st} method:**

_{}

**2 ^{nd} method:**

It is a known result that: _{}when _{}

It is true in particular when _{}

_{}

_{} because O(
) notation allows multiplication

**3 ^{rd} method**

Let: _{}

_{}

_{}

Therefore, for values of n superior to 4, the function f is decreasing. On top of that:

_{}

We can conclude:

_{}

What we have proved by the last relation is exactly:

_{} (above we
have n0 = 4 and c =1)

_{}

Nothing can be said about the relative performance of the two algorithms. O(n^3) could mean n^1/2 as well as n^3.

_{}

**1 ^{st} method:**

_{}

We have proved here that:

_{} n0 =
0 and c= 1

**2 ^{nd} method:**

_{}

_{}

**1 ^{st} method:**

_{}

**2 ^{nd} method:**

Suppose I have n0 and c such that:

_{}

This last proposition doesn't make sense, so the supposition must be false.