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; $fin O(1/n)$ if and only if $1/f in Omega(n)$. Let $fin O(1/n)$. Then there exist $n_0,M>0$ such that for all $n>n_0$, $fleq M/n$. Then $1/fgeq n/M$ for all $n>n_0$, thus $1/fin 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
