Share
Explore BrainMass

Big-O, Big-Omega, Big-Theta

Let f, g, h, and k be the following functions:

f(x) = 3*(x^2) + 4*ln(x) + 9

g(x) = x^2

h(x) = x^5

k(x) = 1 [the constant function "1"]

Throughout the statement and solution to this problem, a caret ("^") denotes that the number immediately following it is an exponent.

----------------------------------------------------------

Show the following:

(a) f = Theta(g)

(b) f = O(h)

(c) f = Omega(k)

(d) f is an unimpressive time-cost function for a sorting algorithm.

Solution Preview

f(x) = 3*(x^2) + 4*ln(x) + 0

(a) g(x) = x^2

Show that f = Theta(g):

Recall that f = Theta(g) if and only if f = O(g) and f = Omega(g).

-----------------------------------

First, we show that f = O(g).

Recall that f = O(g) if and only if there exist constants x_0, c such that

(for all x >= x_0)[f(x) <= c*g(x)]

(">=" denotes "greater than or equal to", and "<=" denotes "less than or equal to")

Note that

(for all x >= 1)[ln(x) <= (x^2)]

Hence for all x >= 1,

4*ln(x) <= 4*(x^2)

Note also that

(for all x >= 1)[1 <= (x^2)]

Hence for all x >= 1,

9 = 9*1 <= 9*(x^2)

Combining these results, we find that, for all x >= 1,

f(x) = 3*(x^2) + 4*ln(x) + 9 <= ...

Solution Summary

A detailed proof is given for the solution to each part of this problem. In the proofs, the definitions of Big-O, Big-Omega, and Big-Theta are recalled and applied.

$2.19