1
$\begingroup$

We know that $f(n) \in O(g(n))$ notation means shortly, that $f(n) \leq cg(n)$ for $n>n_o$ where n and c are some positive constants. And actually it gives the behavior of $f$ as $n$ goes to infinity.

But in the case $f(n) \in O(\frac{1}{n})$ where n is at most 1, shouldn't be more intuitive to say that the behavior of $f$ as $n$ goes to zero (and not to infinity) is $\frac{1}{n}$?

For example if $f$ gives the space consumption of an algorithm, then $f \in O(\frac{1}{n^2})$ is a lot better from $f \in O(\frac{1}{n})$ if we allow n>1. But if for any reason algorithm is restricted in the range $n \in [0,1]$ then we would like $f$ resembles $\frac{1}{n}$ and not $\frac{1}{n^2}$.

To make things even weirder suppose that $f(n) \leq \frac{1}{n}+\frac{1}{n^2}$. For n>1 the dominant term is the $\frac{1}{n}$ and someone could easily say that $f(n) \in O(1/n)$. But if we restrict $n$ to be in $[0,1]$, the dominant term is the $\frac{1}{n^2}$. In that case is it right to say $f\in O(\frac{1}{n^2})$?

$\endgroup$
3
  • 1
    $\begingroup$ It is impossible for an algorithm to have asymptotically decreasing runtime, because it takes linear time just to read the input. So in practice this isn't an issue (at least in computer science). $\endgroup$ – gardenhead Mar 17 '17 at 3:32
  • $\begingroup$ gerdenhead, I edited my question so f now is the space consumption of an algorithm $\endgroup$ – Curious_Dim Mar 17 '17 at 3:37
  • 1
    $\begingroup$ The issue is not time vs space, rather it is the meaning of the parameter $n$. It could be the error of some algorithm, for example (so $n$ is not the perfect symbol to use here). $\endgroup$ – Yuval Filmus Mar 17 '17 at 11:33
1
$\begingroup$

In this context it is clear that big O is taken as $n\to0$, rather than $n\to\infty$ as is more usual for us. For a function $f(x)$ defined on $(0,1)$, we say that $f(x) = O(1/x)$ if there exists a constant $C>0$ such that $f(x) < C/x$ (or, depending on the exact definition, $|f(x)| < C/x$.

This definition is by and large equivalent to the more usual definition which states that $f(x) = O(1/x)$ if there exist two constants $x_0 \in (0,1)$ and $C>0$ such that $f(x) < C/x$ for all $x \leq x_0$.

If you are confused, note that $f(x) = O(1/x)$ under these definitions iff $g(n) = O(n)$ under the usual definition, where $g(n) = f(1/n)$.

For $n$ in this range, we usually use symbols like $\epsilon$ or $\delta$ to emphasize that we are taking the asymptotics as the variable tends to 0 rather than as the variable tends to infinity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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