[Solved]: Complexity inversely propotional to $n$

Problem Detail: Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?

Asked By : mmdemirbas

Answered By : Peter

Consider an algorithm with some running time bounded by $f(n)$ and suppose that $f(n) in O(1/n)$. That means that there is some constant $c$ such that for sufficiently large values of $n$, it holds that $$f(n) leq cfrac{1}{n}.$$ Clearly, for any fixed $c$ and sufficiently large $n$, the right side will be strictly less than $1$, which requires $f(n)=0$, since $f$ maps to $mathbb{N}$. In my understanding, even an algorithm that immediately terminates, takes at least $1$ step (namely to terminate), i.e., $forall ncolon f(n)ge 1$. So no such algorithm can exist.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3495  Ask a Question  Download Related Notes/Documents