Are there any O(1/n) algorithms?
Or anything else which is less than O(1)?
Are there any O(1/n) algorithms?
Or anything else which is less than O(1)?
This question isn't as silly as it might seem to some. At least theoretically, something such as O(1/n) is completely sensible when we take the mathematical definition of the Big O notation:
Now you can easily substitute g(x) for 1/x … it's obvious that the above definition still holds for some f.
For the purpose of estimating asymptotic run-time growth, this is less viable … a meaningful algorithm cannot get faster as the input grows. Sure, you can construct an arbitrary algorithm to fulfill this, e.g. the following one:
def get_faster(list):
how_long = (1 / len(list)) * 100000
sleep(how_long)
Clearly, this function spends less time as the input size grows … at least until some limit, enforced by the hardware (precision of the numbers, minimum of time that sleep
can wait, time to process arguments etc.): this limit would then be a constant lower bound so in fact the above function still has runtime O(1).
But there are in fact real-world algorithms where the runtime can decrease (at least partially) when the input size increases. Note that these algorithms will not exhibit runtime behaviour below O(1), though. Still, they are interesting. For example, take the very simple text search algorithm by Horspool. Here, the expected runtime will decrease as the length of the search pattern increases (but increasing length of the haystack will once again increase runtime).
Yes.
There is precisely one algorithm with runtime O(1/n), the "empty" algorithm.
For an algorithm to be O(1/n) means that it executes asymptotically in less steps than the algorithm consisting of a single instruction. If it executes in less steps than one step for all n > n0, it must consist of precisely no instruction at all for those n. Since checking 'if n > n0' costs at least 1 instruction, it must consist of no instruction for all n.
Summing up: The only algorithm which is O(1/n) is the empty algorithm, consisting of no instruction.
sharptooth is correct, O(1) is the best possible performance. However, it does not imply a fast solution, just a fixed time solution.
An interesting variant, and perhaps what is really being suggested, is which problems get easier as the population grows. I can think of 1, albeit contrived and tongue-in-cheek answer:
Do any two people in a set have the same birthday? When n exceeds 365, return true. Although for less than 365, this is O(n ln n). Perhaps not a great answer since the problem doesn't slowly get easier but just becomes O(1) for n > 365.
That's not possible. The definition of Big-O is the not greater than inequality:
A(n) = O(B(n))
<=>
exists constants C and n0, C > 0, n0 > 0 such that
for all n > n0, A(n) <= C * B(n)
So the B(n) is in fact the maximum value, therefore if it decreases as n increases the estimation will not change.
From my previous learning of big O notation, even if you need 1 step (such as checking a variable, doing an assignment), that is O(1).
Note that O(1) is the same as O(6), because the "constant" doesn't matter. That's why we say O(n) is the same as O(3n).
So if you need even 1 step, that's O(1)... and since your program at least needs 1 step, the minimum an algorithm can go is O(1). Unless if we don't do it, then it is O(0), I think? If we do anything at all, then it is O(1), and that's the minimum it can go.
(If we choose not to do it, then it may become a Zen or Tao question... in the realm of programming, O(1) is still the minimum).
Or how about this:
programmer: boss, I found a way to do it in O(1) time!
boss: no need to do it, we are bankrupt this morning.
programmer: oh then, it becomes O(0).
No, this is not possible:
As n tends to infinity in 1/n we eventually achieve 1/(inf), which is effectively 0.
Thus, the big-oh class of the problem would be O(0) with a massive n, but closer to constant time with a low n. This is not sensible, as the only thing that can be done in faster than constant time is:
void nothing() {};
And even this is arguable!
As soon as you execute a command, you're in at least O(1), so no, we cannot have a big-oh class of O(1/n)!
What about not running the function at all (NOOP)? or using a fixed value. Does that count?
I often use O(1/n) to describe probabilities that get smaller as the inputs get larger -- for example, the probability that a fair coin comes up tails on log2(n) flips is O(1/n).
O(1) simply means "constant time".
When you add an early exit to a loop[1] you're (in big-O notation) turning an O(1) algorithm into O(n), but making it faster.
The trick is in general the constant time algorithm is the best, and linear is better then exponential, but for small amounts of n, the exponential algorith might actually be faster.
1: Assuming a static list length for this example
many people have had the correct answer (No) Here's another way to prove it: In order to have a function, you have to call the function, and you have to return an answer. This takes a certain constant amount of time. EVEN IF the rest of the processing took less time for larger inputs, printing out the answer (Which is we can assume to be a single bit) takes at least constant time.
I believe quantum algorithms can do multiple computations "at once" via superposition...
I doubt this is a useful answer.
If solution exists, it can be prepared and accessed in constant time=immediately. For instance using a LIFO data structure if you know the sorting query is for reverse order. Then data is already sorted, given that the appropriate model (LIFO) was chosen.
Which problems get easier as population grows? One answer is a thing like bittorrent where download speed is an inverse function of number of nodes. Contrary to a car, which slows down the more you load it, a file-sharing network like bittorrent speeds the more nodes connected.
You can't go below O(1), however O(k) where k is less than N is possible. We called them sublinear time algorithms. In some problems, Sublinear time algorithm can only gives approximate solutions to a particular problem. However, sometimes, an approximate solutions is just fine, probably because the dataset is too large, or that it's way too computationally expensive to compute all.
As has been pointed out, apart from the possible exception of the null function, there can be no O(1/n)
functions, as the time taken will have to approach 0.
Of course, there are some algorithms, like that defined by Konrad, which seem like they should be less than O(1)
in at least some sense.
def get_faster(list):
how_long = 1/len(list)
sleep(how_long)
If you want to investigate these algorithms, you should either define your own asymptotic measurement, or your own notion of time. For example, in the above algorithm, I could allow the use of a number of "free" operations a set amount of times. In the above algorithm, if I define t' by excluding the time for everything but the sleep, then t'=1/n, which is O(1/n). There are probably better examples, as the asymptotic behavior is trivial. In fact, I am sure that someone out there can come up with senses that give non-trivial results.
What about this:
void FindRandomInList(list l)
{
while(1)
{
int rand = Random.next();
if (l.contains(rand))
return;
}
}
as the size of the list grows, the expected runtime of the program decreases.
constains
is O(1)
O(1/n) is not less then O(1), it basically means that the more data you have, the faster algorithm goes. Say you get an array and always fill it in up to a 10100 elements if it has less then that and do nothing if there's more. This one is not O(1/n) of course but something like O(-n) :) Too bad O-big notation does not allow negative values.
Most of the rest of the answers interpret big-O to be exclusively about the running time of an algorithm. But since the question didn't mention it, I thought it's worth mentioning the other application of big-O in numerical analysis, which is about error.
Many algorithms can be O(h^p) or O(n^{-p}) depending on whether you're talking about step-size (h) or number of divisions (n). For example, in Euler's method, you look for an estimate of y(h) given that you know y(0) and dy/dx (the derivative of y). Your estimate of y(h) is more accurate the closer h is to 0. So in order to find y(x) for some arbitrary x, one takes the interval 0 to x, splits it up until n pieces, and runs Euler's method at each point, to get from y(0) to y(x/n) to y(2x/n), and so on.
So Euler's method is then an O(h) or O(1/n) algorithm, where h is typically interpreted as a step size and n is interpreted as the number of times you divide an interval.
You can also have O(1/h) in real numerical analysis applications, because of floating point rounding errors. The smaller you make your interval, the more cancellation occurs for the implementation of certain algorithms, more loss of significant digits, and therefore more error, which gets propagated through the algorithm.
For Euler's method, if you are using floating points, use a small enough step and cancellation and you're adding a small number to a big number, leaving the big number unchanged. For algorithms that calculate the derivative through subtracting from each other two numbers from a function evaluated at two very close positions, approximating y'(x) with (y(x+h) - y(x) / h), in smooth functions y(x+h) gets close to y(x) resulting in large cancellation and an estimate for the derivative with fewer significant figures. This will in turn propagate to whatever algorithm you require the derivative for (e.g., a boundary value problem).
I guess less than O(1) is not possible. Any time taken by algo is termed as O(1). But for O(1/n) how about the function below. (I know there are many variants already presented in this solution, but I guess they all have some flaws (not major, they explain the concept well). So here is one, just for the sake of argument:
def 1_by_n(n, C = 10): #n could be float. C could be any positive number
if n <= 0.0: #If input is actually 0, infinite loop.
while True:
sleep(1) #or pass
return #This line is not needed and is unreachable
delta = 0.0001
itr = delta
while delta < C/n:
itr += delta
Thus as n increases the function will take less and less time. Also it is ensured that if input actually is 0, then the function will take forever to return.
One might argue that it will be bounded by precision of machine. thus sinc eit has an upper bound it is O(1). But we can bypass that as well, by taking inputs of n and C in string. And addition and comparison is done on string. Idea is that, with this we can reduce n arbitrarily small. Thus upper limit of the function is not bounded, even when we ignore n = 0.
I also believe that we can't just say that run time is O(1/n). But we should say something like O(1 + 1/n)
OK, I did a bit of thinking about it, and perhaps there exists an algorithm that could follow this general form:
You need to compute the traveling salesman problem for a 1000 node graph, however, you are also given a list of nodes which you cannot visit. As the list of unvisitable nodes grows larger, the problem becomes easier to solve.
I see an algorithm that is O(1/n) admittedly to an upper bound:
You have a large series of inputs which are changing due to something external to the routine (maybe they reflect hardware or it could even be some other core in the processor doing it.) and you must select a random but valid one.
Now, if it wasn't changing you would simply make a list of items, pick one randomly and get O(1) time. However, the dynamic nature of the data precludes making a list, you simply have to probe randomly and test the validity of the probe. (And note that inherently there is no guarantee the answer is still valid when it's returned. This still could have uses--say, the AI for a unit in a game. It could shoot at a target that dropped out of sight while it was pulling the trigger.)
This has a worst-case performance of infinity but an average case performance that goes down as the data space fills up.
In numerical analysis, approximation algorithms should have sub-constant asymptotic complexity in the approximation tolerance.
class Function
{
public double[] ApproximateSolution(double tolerance)
{
// if this isn't sub-constant on the parameter, it's rather useless
}
}
I'm no expert, but I thought about a unique scenario;
For a set of unknown elements, where N is the number of known elements and where f(N) confirms a known element from an unknown element:
The state of any element is dependent on the existential state of every other element.
Consider a set of 1 element
It is nearly impossible to confirm a known element as the only element in existence is unknown.
Consider a set of 2 elements
It is possible that we will eventually know the existence of the other element, but since we must wait for both elements to assert both their existences and the existence of their partner, it is difficult to tell when that'll be.
Consider a set of 3 elements
Since, the state of the third element is tied directly to the state of the other 2 elements, we can state that once we know 2 elements, it is far more likely that we will know the third element. But since, N is the number of known elements, as N increases, it is far more likely to confirm the known state of all 3 elements.
Consider a set of infinite elements
If we were to ascertain the state of every other element by slowly deducing from the state of a singular element, it will take infinite time. If however, we know an infinite number of elements, it will take close to zero amount of time to confirm the existence of any element.
This algorithm will eventually hit O(0) complexity, however observing reality is technically a step in the process. Therefore, we can say that this O(1/N) is O(0) for N=infinity; however is really O(1) where constant is basically zero.
An argument can be made that for discovery, the complexity is O(1), since the act of observing is taken as an input and output for the observer. However, the discovery algorithm is irrelated as to whether or not an observer performed an observation. The algorithm simply discovers pre-existing states based on previous discoveries. When a pre-existing state is discovered, more elements can be discovered and assumed to be a state. The act of assumption is also irrelated to the algorithm, as the algorithm simply knows that things are more true once more things are true.
For ever increasing set sizes, the algorithm gets increasingly faster. The difference between a small set and a large set size is similar to a person getting a gift and not knowing what is inside versus the giver who has more material knowledge and thereby knows the contents.
Although it may seem arbitrary, this is very similar to properties of entanglement with reference to entangled particles. A scientist might need to take some fixed time to measure a pair of particles and confirm their states. However, each particle isn't communicating with their partner, but rather existing with respect to each other.
Thereby, we can deduce without knowing the existence of another particle that as long as they are entangled, we will can affirm the potential states of the particles without ever observing. With more particles of the "whole object", it becomes easier to recognize and discover the entirety of the object. With less information, it becomes a messy problem of probabilities.
O(1)
time just to generate and return back a trivial answer.
Commented
Aug 31, 2023 at 3:59
1
computation step for any input size has complexity O(1)
. To beat this for large n
, your algorithm needs to need 0
computation steps for n
above a certain threshold. Which is O(0)
. So there is no complexity fitting between O(0)
and O(1)
.
Commented
Sep 1, 2023 at 5:58
0
. The speed at which something is discovered is then based on a probability between O(0)
and O(1)
as the state exists somewhere in between a step and not a step.
Commented
Sep 2, 2023 at 21:56
0
and 1
for all sufficiently large sets because we can state that it is both known and unknown. However, we also know that the algorithm will know more if more elements are discovered. Therefore, the more known elements are closer to O(0)
than O(1)
and vice versa. If you use the universe as a computation model, then this is how particles behave.
Commented
Sep 2, 2023 at 21:57
inline void O0Algorithm() {}
It may be possible to construct an algorithm that is O(1/n). One example would be a loop that iterates some multiple of f(n)-n times where f(n) is some function whose value is guaranteed to be greater than n and the limit of f(n)-n as n approaches infinity is zero. The calculation of f(n) would also need to be constant for all n. I do not know off hand what f(n) would look like or what application such an algorithm would have, in my opinion however such a function could exist but the resulting algorithm would have no purpose other than to prove the possibility of an algorithm with O(1/n).
No, there are no algorithms with a time complexity of O(1/n) because it violates the fundamental rule of Big O notation, which is that the runtime must be a constant multiple of the input size. In other words, the time complexity must be expressed as a function of n, the size of the input. O(1/n) is not a valid function of n because it decreases as n increases, which means that the algorithm would be faster for larger inputs, which contradicts the notion of scalability.
If the answer is the same regardless of the input data then you have an O(0) algorithm.
or in other words - the answer is known before the input data is submitted - the function could be optimised out - so O(0)
Big-O notation represents the worst case scenario for an algorithm which is not the same thing as its typical run time. It is simple to prove that an O(1/n) algorithm is an O(1) algorithm . By definition,
O(1/n) --> T(n) <= 1/n, for all n >= C > 0
O(1/n) --> T(n) <= 1/C, Since 1/n <= 1/C for all n >=C
O(1/n) --> O(1), since Big-O notation ignores constants (i.e. the value of C doesn't matter)
hashtable-contains
algorithm which can be denoted as O(1) -- and the worst case can be given very precisely as Theta(n)! Omega and Theta may simply be used to denote other bounds but to say it again: they have got nothing to do with average or best case.
Commented
May 25, 2009 at 14:17
Nothing is smaller than O(1) Big-O notation implies the largest order of complexity for an algorithm
If an algorithm has a runtime of n^3 + n^2 + n + 5 then it is O(n^3) The lower powers dont matter here at all because as n -> Inf, n^2 will be irrelevant compared to n^3
Likewise as n -> Inf, O(1/n) will be irrelevant compared to O(1) hence 3 + O(1/n) will be the same as O(1) thus making O(1) the smallest possible computational complexity
I don't know about algorithms but complexities less than O(1) appear in randomized algorithms. Actually, o(1) (little o) is less than O(1). This kind of complexity usually appears in randomized algorithms. For example, as you said, when the probability of some event is of order 1/n they denote it with o(1). Or when they want to say that something happens with high probability (e.g. 1 - 1/n) they denote it with 1 - o(1).