Question

• The two parts of this exercise describe

the relationship between little-o and big-O notation.

a) Show that if f (x) and g(x) are functions such that

f (x) is o(g(x)), then f (x) is O(g(x)).

b) Show that if f (x) and g(x) are functions such that

f (x) is O(g(x)), then it does not necessarily follow

that f (x) is o(g(x)).

Short answer

Subpart (a):Show that if f (x) and g(x) are functions such that f (x) is o(g(x)), then f (x) is O(g(x)).

Step-by-step solution

Step 1:

As we know, $\stackrel{lim}{x\to \infty }$f(x)/g(x) = 0, |f (x)|/|g(x)| < 1 for sufficiently large x.

Step 2:

Hence, |f (x)| < |g(x)| for x>k for some constant k. Therefore, f (x) is O(g(x)).

Subpart (b): Show that if f (x) and g(x) are functions such that f (x) is O(g(x)), then it does not necessarily follow that f (x) is o(g(x)).Step 1:

Let f (x) = g(x) = x.

Step 2:

Then f (x) is O(g(x)), but f (x) is not o(g(x)) because f (x)/g(x) = 1.

So, these are the answers.