Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What I figured is that it means that the function has an upper bound, however I came across this text:enter image description here

Here since g(x) either equal or less to f(x), |g(x) / f(x)| must be bounded right? Since the denominator is greater than the numerator in this case, the value of the fraction can't exceed a lot.

What am I interpreting wrong here?

share|improve this question
2  
Bounded means bounded above and below. The function $-x^2$ is not bounded. In most applications to algorithms, it doesn't matter, since the functions are naturally non-negative, so are bounded below by $0$. But in principle one should be careful. The function $f(x)$ is bounded if and only if $|f(x)|$ is bounded above. –  André Nicolas Feb 10 '13 at 5:43
    
Have you looked at en.wikipedia.org/wiki/Big_O_notation in depth? –  JB King Feb 10 '13 at 5:44
add comment

1 Answer

A function $f: D \to \mathbb{R}$ is said to be bounded if there exists a constant $C>0$ such that $|f(x)| \le C$ for all $x\in D$. So it is both lower- and upper- bounded. And $C$ need not be less than $1$.

The big-$O$ notation gives something else, called asymptotic bound. Don't mix up.

share|improve this answer
    
Indeed, if $|f(x)/g(x)|$ is bounded, so is $|g(x)/f(x)|$. If one bound is $C$, the other is $1/C$. –  Laura Balzano Feb 10 '13 at 5:52
3  
Not really. See what if $f(n)=n$ and $g(n) = n^2$ where $n\in\mathbb{N}^*$. –  Robin Feb 10 '13 at 5:57
    
Oops, Thank you @Robin! –  Laura Balzano May 21 '13 at 20:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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