2

If f(x) = O(g(x)) as x -> infinity, then

A. g is the upper bound of f

B. f is the upper bound of g.

C. g is the lower bound of f.

D. f is the lower bound of g.

Can someone please tell me when they think it is and why?

2
  • 1
    Have you looked at something like en.wikipedia.org/wiki/Big_O_notation? It gives definitions for what this notation means. Apr 30, 2011 at 15:08
  • 1
    Folks, I'm considering Big O notation as on the fence enough to be on topic, since it is used in so many answers here. You're free to disagree with me, but I'm not closing this.
    – user50049
    Apr 30, 2011 at 17:15

3 Answers 3

3

The real answer is that none of these is correct.

The definition of big-O notation is that:

|f(x)| <= k|g(x)|

for all x > x0, for some x0 and k.

In specific cases, |k| might be less than or equal to 1, in which case it would be correct to say that "|g| is the upper bound of |f|". But in general, that's not true.

1
  • Shouldn't the last paragraph have "|g| is an upper bound of f"? With the definition you have, x is O(-x^2). May 1, 2011 at 6:09
1

Answer

g is the upper bound of f

When x goes towards infinity, worst case scenario is O(g(x)). That means actual exec time can be lower than g(x), but never worse than g(x).

EDIT:

As Oli Charlesworth pointed out, that is only true with arbitrary constant k <= 1 and not in general. Please look at his answer for the general case.

8
  • @oli: k represents what? constants?
    – usoban
    Apr 30, 2011 at 15:25
  • @user: Unfortunately, it's not! "k.g is the upper bound of f" would be correct. Apr 30, 2011 at 15:25
  • @usoban: Yes, an arbitrary constant. Apr 30, 2011 at 15:26
  • if we're that strict, it's k*g(x)+a :)
    – usoban
    Apr 30, 2011 at 15:28
  • 2
    @usoban: Because the definition of Big-O is that |f(n)| <= k|g(n)| for all n > n0, where n0 and k are constants to be found. Your answer assumes that k=1. Apr 30, 2011 at 15:54
0

The question checks your understanding of the basics of asymptotic algebra, or big-oh notation. In

f(x) = O(g(x)) as x approaches infinity

the question says that when you feed the function f a value x, the value which f computes from x is then in the order of that returned from another function, g(x). As an example, suppose

f(x) = 2x
g(x) = x

then the value g(x) returns when fed x is of the same order as that f(x) returns for x. Specifically, the two functions return a value that is in the order of x; the functions are both linear. It doesn't matter whether f(x) is 2x or ½x; for any constant factor at all f(x) will return a value that is in the order of x. This is because big-oh notation is about ignoring constant factors. Constant factors don't grow as x grows and so we assume they don't matter nearly as much as x does.

We restrict g(x) to a specific set of functions. g(x) can be x, or ln(x), or log(x) and so on and so forth. It may look as if when

f(x) = 2x
g(x) = x

f(x) yields values higher than g(x) and therefore is the upper bound of g(x). But once again, we ignore the constant factor, and we say that the order-of upper bound, which is what big-oh is all about, is that of g(x).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.