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.

If $f$ is $O(g)$ over some base, this means that $f(x) = \beta(x)g(x)$, where $\beta$ is eventually bounded. So this means that eventually, $f$ is at most $c$ times $g$, where $c$ is some constant.

But I thought $O$ was a way of expressing that two functions are eventually approximately the same. In that case, this seems like a poor definition. If $g$ is unbounded, then the difference between $f$ and $g$ is also unbounded, so the two functions might be $O$ of one another and yet still diverge wildly.

I would have used an additive definition: $f(x)=g(x)+\beta(x)$, where $\beta$ is eventually bounded. So then we know that $f(x)=g(x)\pm \epsilon$, where $\epsilon$ is some positive constant. We now have a statement on the error incurred by assuming $f=g$.

Similar objections can be raised against the definition of asymptotic equivalence. $x^2\sim x^2+x$ as $x\rightarrow+\infty$ even though their difference grows without bound. So in what sense are they equivalent?

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

To appreciate these comparisons we have to look at some actual numbers. Let's take the case of $x^2+x$ vs. $x^2$. Let's suppose a calculation takes a millisecond and we have one algorithm $A_1$ that takes $x^2$ calculations to complete a task and another algorithm $A_2$ that takes $x^2+x$ calculations to complete the same task where $x$ is the problem size.

If $x=1,000,000$ then $A_1$ takes $10^{12}$ milliseconds which is $10^9$ seconds which is about $31.7$ years. $A_2$ takes $10^{12} + 10^6$ milliseconds which is $10^9 + 10^3$ seconds and since $10^3$ seconds is $16$ minutes and $40$ seconds $A_2$ takes about $31.7$ years and an additional $17$ minutes. Is that significant?

share|improve this answer
add comment

$f=O(g)$ expresses that eventually $f \ll g$, not that they are eventually approximately the same.

As far as equivalence itself, which is denoted $f=\Theta(g)$, we want to denote equivalence up to a constant factor in input size, because you want to talk about orders. In other words, $x^2 \ll 5x^2$, but the difference is not that of an order, i.e. $\dfrac{x^2}{5x^2}$ would converge to $5$, not to $0$, which is what you want to capture by this definition.

I guess to make it explicit with your example. $x^2$ and $x^2+x$ are equivalent in the sense that

$$ \lim_{x \to \infty} \frac{x^2}{x^2+x} = 1 \in \mathbb{R}^+, $$

importantly, not in $\{0,\infty\}$. That classifies them of the same order...

share|improve this answer
    
For equivalence, you just seem to be repeating the definition - I agree with what you're saying, but what is the motivation for such a definition? Why should it interest anyone that the ratio between two functions tends to $1$? –  Jack M Jun 12 '13 at 13:13
    
@JackM You want to define the difference of an order. I.e., $f \neq \Theta(g)$ means there is an order difference between the two. (By the way, this is why $O$ was chosen, as the first letter of the word 'order'). E.g. in algorithms, it is less critical to know things within constant factor (you can manipulate the state space of the Turing machine to get what you want), but the order differences are very noticeable. –  gt6989b Jun 12 '13 at 13:21
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.