[Solved]: Expressing that a function converges to 1 with linear rate using Landau notation

Problem Detail: 

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?

Asked By : Erel Segal-Halevi

Answered By : Tom van der Zanden

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44187

 Ask a Question

 Download Related Notes/Documents