Are there any O(1/n) algorithms

[Shalmanese]

In an Algos lecture, someone asked if there were any algorithms that ran in O(1/n) time. Do they exist?

 

[Mday]

dunno, an algorithm that gets more efficient as more variables are placed into it....

there may be some that do follow that trend up to a certain point, then efficiency wears off...

i know O notation does not refer to efficiency, but it's what it boils down to in the end.

 

[Peter]

Here's one ...

(1) Look at complexity of task.
(2) Think about doing the task.
(3) Run away.

The time spent in (2) is getting proportionally shorter with the task getting bigger 😉

 

[DML1001]

It may TECHNICALLY be possible to have a O(1/n) algorithm, but only a very stupid one.

O notation gives you an upper bound on the complexity, so a O(n) algorithm can also be legally be called a O(n^2) algorithm. Thus, I suppose you could consider a NULL algorithm that does nothing regardless of input to be a O(1/n) algorithm.

Since a blank algorithm that does nothing requires no time to run (in theory anyway), I guess you could consider it to be O(1/n) since zero is always <= 1/n even in the limit as n -> infinity.

However, I don't see how any such REAL algorithm could exist, since O(1/n) would imply that the algorithm takes no time to run on an infinite input.

Anyway, ignoring infinites for a moment, its still impossible to have anything run in O(1/n). As one of the above posters said, you might be able to do it for a little, but sooner or later, no matter what constant you have hidden by the O notation, your still gonna be screwed eventually.

 

[TheDoktor]

Even if you find such an algorithm, it would probably be useless to you because it may have something to do with size of the input but not with the content of the input.

 

[Chu]

Originally posted by: Shalmanese
In an Algos lecture, someone asked if there were any algorithms that ran in O(1/n) time. Do they exist?

Interesting question. Technically, any O(1) task is also O(1/n), but I am assuming you are looking for something that is Omega(1/n). A good way to approach this problem would be to construct a recurrance relation that is O(1/n) and see if you can think of any possible algorithm that would fit, however my brain is curretly on vacation (I had a REALLY rough summer semester) so you're on your own to tackle this problem 😀

-Chu

 

[Noriaki]

Originally posted by: Chu
Technically, any O(1) task is also O(1/n)

No it isn't...
O(1) = O(n^0)
O(1/n) = O(n^-1)

O is an upper bound on running time, so anything that is O(n^c) is also O(n^(c+k)), but it is not in general O(n^(c-k)) (k > 0).

Saying that something that is O(1) is also O(1/n) is just like saying something that is O(n) is also O(1) or something that is O(n^2) is also O(n), doesn't work decreasing powers. Because O does not have to be a tight bound, you can increase the power of n if you want (though you lose 'tightness'), but you can't decrease it.

Omega is lower bound, so any Om(1) task is also Om(1/n), but not for O.

An easy example of an O(1) task is selecting the first item of a list. This is not O(1/n) (ie it gets faster as the list gets bigger).

 

[TheDoktor]

Interesting question. Technically, any O(1) task is also O(1/n)

-Chu

The best way to describe why this isn't true is that when N goes to infinity, 1/n goes to zero and if N is large enough 1/n will be smaller than and constant > 0, including 1.