3
$\begingroup$

I am working on an algorithm which approximates a certain optimal quantity. The approximation becomes better when the size of the problem ($n$) becomes larger: the difference from the optimum is approximately $1/n$.

Initially, I wrote that the algorithm achieves an approximation of:

$$\Omega(1-1/n)$$

But, now I am not sure this notation is correct: it is just like writing $\Omega(1)$ (the smaller element is swallowed in the larger element, which is 1).

Should I write:

$$1-O(1/n)$$

Or maybe:

$$1-1/\Omega(n)$$

Which of these is the correct notation?

$\endgroup$
  • 2
    $\begingroup$ You might even write the more precise statement $1 - \frac{1}{n} + o(\frac{1}{n})$, if that is an accurate description of the error! (that's little-oh) $\endgroup$ – Hurkyl Jul 6 '15 at 19:33
  • $\begingroup$ The error is something like $1-const/n+1/n^2...$ $\endgroup$ – Erel Segal-Halevi Jul 7 '15 at 5:07
  • $\begingroup$ "What is the best use of Landau notation for denoting approximation qualities?" This doesn't make sense. What the function is being used to measure is irrelevant to what notation you should use. It's like saying, "$d(x,y)$ is the distance from $x$ to $y$. Should I write $d(x,y)<k$ or $d(x,y)>k$?" The answer would depend on how the function relates to $k$, not on the fact that it's measuring distance. $\endgroup$ – David Richerby Jul 7 '15 at 12:54
  • $\begingroup$ @DavidRicherby this is not my original title. I am not sure what is the best title for this question. $\endgroup$ – Erel Segal-Halevi Jul 7 '15 at 13:11
  • 1
    $\begingroup$ @ErelSegal-Halevi Perhaps something like, "Landau notation for functions whose limit is 1" or "... that don't grow to infinity"? $\endgroup$ – David Richerby Jul 7 '15 at 13:13
5
$\begingroup$

Both of the options you listed are acceptable. They have the same meaning; $f\in O(1/n)$ if and only if $1/f \in \Omega(n)$.

Let $f\in O(1/n)$. Then there exist $n_0,M>0$ such that for all $n>n_0$, $f\leq M/n$. Then $1/f\geq n/M$ for all $n>n_0$, thus $1/f\in \Omega(n)$, since for $n>n_0$, $1/f \geq 1/M \cdot n$.

The other direction is similar.

$\endgroup$
  • $\begingroup$ The first paragraph is only true if you restrict the domain of $f$ suitably; in particular, $f(n) = 0$ has to be excluded. $\endgroup$ – Raphael Jul 6 '15 at 16:00
1
$\begingroup$

What you want to write, I think, is $1 - \Theta(1/n)$, unless you want to be more detailed and fill in the particular value $c$ so that you can write $1 - c/n + O(1/n^2)$.

While $1 - O(1/n)$ is accurate, it's kinda weird because $1 \in 1 - O(1/n)$, and even $1 + 1/n \in 1 - O(1/n)$, but I think it's still saying what you want. Maybe $1 - |O(1/n)|$ would be clearly understood if the sign bothers you like it does me.

$1 - 1/\Omega(n)$ doesn't have the sign problem that $1 - O(1/n)$ does, but it looks weird (and awkward to do calculation with), so I would avoid writing something like that.

$\endgroup$
  • $\begingroup$ I want to say that the difference from the optimum is at most a constant factor times $1/n$. I used $O$ (and not $\Theta$) because in some cases, the difference can be 0, or $1/n^2$, or anything smaller than $1/n$. $\endgroup$ – Erel Segal-Halevi Jul 7 '15 at 5:28

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.