Purchase Solution

Big-O, Big-Omega, Big-Theta

Not what you're looking for?

Ask Custom Question

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.

Purchase this Solution

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.

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 provided by:
Education
  • AB, Hood College
  • PhD, The Catholic University of America
  • PhD, The University of Maryland at College Park
Recent Feedback
  • "Thanks for your assistance. "
  • "Thank you. I understand now."
  • "Super - Thank You"
  • "Very clear. I appreciate your help. Thank you."
  • "Great. thank you so much!"
Purchase this Solution


Free BrainMass Quizzes
Basic Networking Questions

This quiz consists of some basic networking questions.

Basic Computer Terms

We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.

Basic UNIX commands

Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.

C# variables and classes

This quiz contains questions about C# classes and variables.

C++ Operators

This quiz tests a student's knowledge about C++ operators.