Explore BrainMass

Explore BrainMass

    Big-O, Big-Omega, Big-Theta

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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.

    © BrainMass Inc. brainmass.com December 15, 2022, 7:02 pm ad1c9bdddf

    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.