Q:

Algorithm whose worst case complexity is inversely proportional to input size?

Possible Duplicate:
Are there any O(1/n) algorithms? 

Any algorithm whose complexity decreases with increase in input size?
I am talking about worst case performance.
In general we know math graphs whose magnitude decreases with the input size but do we have any meaningful algo that matches these graphs?

A:

How about this?
 Mystery(array[1..n])
 1. x := fn(0)
 2. for i = 1 to floor(1,000,000 / n) do
 3.    x = fn(x)
 4. return x

All such algorithms are constant-time, asymptotically speaking, for obvious reasons.
EDIT:
Actually, this is asymptotically O(log n), if integer division is logarithmic, which I believe it is. http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations As such, my answer would be that there aren't really any O(1/n) algorithms. O(1) is the smallest complexity class there is... unless there's a way to make an algorithm that can know the inverse of its input size without computing it!
EDIT2:
I just thought of perhaps passing 1,000,000 / n to the function as input... but that's not really a genuine solution, since the algorithm would have no way to tell if that condition were violated, and the caller would need to compute it anyway. Note that a lot of this discussion isn't particularly relevant if you're taking arithmetic operations to be constant time, as I'm pretty sure they are on computers with fixed-size intrinsic types and instruction sets operating on defined register sizes.

