[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 c\frac{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 n\colon 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