364

Are there any O(1/n) algorithms?

Or anything else which is less than O(1)?

7
  • Most of the questions assume you mean "Are there any algorithms with a time complexity of O(1/n)?" Shall we assume this is the case? Big-O (and Big-Theta, etc.) describe functions, not algorithms. (I know of no equivalence between functions and algorithms.)
    – jyoungdev
    Commented Jul 8, 2010 at 22:43
  • 5
    That is the commonly understood definition of "O(X) algorithm" in computer science: an algorithm whose time complexity is O(X) (for some expression X).
    – David Z
    Commented Jul 9, 2010 at 1:17
  • 2
    I have heard such bound in case of I/O efficient priority queue algorithm using Buffer Tree. In a Buffer Tree, each operation takes O(1/B) I/Os; where B is block size. And total I/Os for n operations is O(n/B.log(base M/B)(n/B)), where log part is the height of the buffer tree.
    – CODError
    Commented Dec 5, 2015 at 1:01
  • There are lots of algorithms with O(1/n) error probability. For example a bloom filter with O(n log n) buckets. Commented May 16, 2016 at 10:21
  • You can't lay an egg faster by adding chickens.
    – Wyck
    Commented Oct 5, 2019 at 1:19

33 Answers 33

340

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).

30
  • 24
    'Enforced by the hardware' also applies to a Turing Machine. In case of O(1/n) there will always be an input size for which the algorithm is not supposed to execute any operation. And therefore I would think that O(1/n) time complexity is indeed impossible to achieve. Commented May 25, 2009 at 14:10
  • 30
    Mehrdad, you don't understand. The O notation is something about the limit (technically lim sup) as n -> ∞. The running time of an algorithm/program is the number of steps on some machine, and is therefore discrete -- there is a non-zero lower bound on the time that an algorithm can take ("one step"). It is possible that upto some finite N a program takes a number of steps decreasing with n, but the only way an algorithm can be O(1/n), or indeed o(1), is if it takes time 0 for all sufficiently large n -- which is not possible. Commented May 25, 2009 at 20:04
  • 32
    We are not disagreeing that O(1/n) functions (in the mathematical sense) exist. Obviously they do. But computation is inherently discrete. Something that has a lower bound, such as the running time of a program -- on either the von Neumann architecture or a purely abstract Turing machine -- cannot be O(1/n). Equivalently, something that is O(1/n) cannot have a lower bound. (Your "sleep" function has to be invoked, or the variable "list" has to be examined -- or the input tape has to be examined on a Turing machine. So the time taken would change with n as some ε + 1/n, which is not O(1/n)) Commented May 26, 2009 at 0:14
  • 17
    If T(0)=∞, it doesn't halt. There is no such thing as "T(0)=∞, but it still halts". Further, even if you work in R∪{∞} and define T(0)=∞, and T(n+1)=T(n)/2, then T(n)=∞ for all n. Let me repeat: if a discrete-valued function is O(1/n), then for all sufficiently large n it is 0. [Proof: T(n)=O(1/n) means there exists a constant c such that for n>N0, T(n)<c(1/n), which means that for any n>max(N0,1/c), T(n)<1, which means T(n)=0.] No machine, real or abstract, can take 0 time: it has to look at the input. Well, besides the machine that never does anything, and for which T(n)=0 for all n. Commented May 27, 2009 at 3:50
  • 46
    You have to like any answer that begins "This question isn't as stupid as it might seem."
    – Telemachus
    Commented Jun 27, 2009 at 12:53
161

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.

10
  • 4
    So if someone asked what the time complexity of an empty algorithm is, you'd answer with O(1/n) ??? Somehow I doubt that.
    – phkahler
    Commented Feb 16, 2010 at 20:42
  • 29
    This is the only correct answer in this thread, and (despite my upvote) it is at zero votes. Such is StackOverflow, where "correct-looking" answers are voted higher than actually correct ones. Commented Feb 24, 2010 at 17:15
  • 5
    No, its rated 0 because it is incorrect. Expressing a big-Oh value in relation to N when it is independent of N is incorrect. Second, running any program, even one that just exists, takes at least a constant amount of time, O(1). Even if that wasn't the case, it'd be O(0), not O(1/n).
    – kenj0418
    Commented Feb 28, 2010 at 17:16
  • 42
    Any function that is O(0) is also O(1/n), and also O(n), also O(n^2), also O(2^n). Sigh, does no one understand simple definitions? O() is an upper bound. Commented Apr 15, 2010 at 3:52
  • 19
    @kenj0418 You managed to be wrong in every single sentence. "Expressing a big-Oh value in relation to N when it is independent of N is incorrect." A constant function is a perfectly goof function. "Second, running any program, even one that just exists, takes at least a constant amount of time, O(1)." The definition of complexity doesn't say anything about actually running any programs. "it'd be O(0), not O(1/n)". See @ShreevatsaR's comment. Commented Aug 24, 2010 at 20:12
25

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.

3
  • 7
    366. Don't forget about leap years! Commented May 25, 2009 at 12:17
  • 2
    You are correct. Like computers, I am occasionally subject to rounding errors :-)
    – Adrian
    Commented May 26, 2009 at 0:14
  • 10
    +1. There are a number of NP-complete problems that undergo a "phase transition" as n increases, i.e. they quickly become much easier or much harder as you exceed a certain threshold value of n. One example is the Number Partitioning Problem: given a set of n nonnegative integers, partition them into two parts so that the sum of each part is equal. This gets dramatically easier at a certain threshold value of n. Commented May 26, 2009 at 11:34
23

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.

16
  • 43
    I suspect this answer is the "right one", but unfortunately I lack the intellect to understand it.
    – freespace
    Commented May 25, 2009 at 6:24
  • 13
    AFAIK this condition does not have to be true for all n, but for all n > n_0 (i.e., only when the size of the input reaches a specific threshold). Commented May 25, 2009 at 7:37
  • 31
    I don't see how the definition (even corrected) contradicts the question of the OP. The definition holds for completely arbitrary functions! 1/n is a completely sensible function for B, and in fact your equation doesn't contradict that (just do the math). So no, despite much consensus, this answer is in fact wrong. Sorry. Commented May 25, 2009 at 8:00
  • 10
    Wrong! I don't like downvoting but you state that this is impossible when there is no clear consensus. In practice you are correct, if you do construct a function with 1/n runtime (easy) it will eventually hit the some minimum time, effectively making it an O(1) algorithm when implemented. There is nothing to stop the algorithm from being O(1/n) on paper though.
    – jheriko
    Commented May 25, 2009 at 9:56
  • 3
    @Jason: Yep, now that you say it... :) @jheriko: A time complexity of O(1/n) does not work on paper IMHO. We're characterizing the growth function f(input size) = #ops for a Turing machine. If it does halt for an input of length n=1 after x steps, then I will choose an input size n >> x, i.e. large enough that, if the algorithm is indeed in O(1/n), no operation should be done. How should a Turing machine even notice this (it's not allowed to read once from the tape)? Commented May 25, 2009 at 13:54
17

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).

2
8

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)!

7

What about not running the function at all (NOOP)? or using a fixed value. Does that count?

7
  • 17
    That's still O(1) runtime. Commented May 25, 2009 at 8:10
  • 2
    Right, that's still O(1). I don't see how someone can understand this, and yet claim in another answer that something less than NO-OP is possible. Commented May 25, 2009 at 20:21
  • 4
    ShreevatsaR: there is absolutely no contradiction. You seem to fail to grasp that big O notation has got nothing to do with the time spent in the function – rather, it describes how that time changes with changing input (above a certain value). See other comment thread for more. Commented May 25, 2009 at 20:42
  • I grasp it perfectly well, thank you. The point — as I made several times in the other thread — is that if the time decreases with input, at rate O(1/n), then it must eventually decrease below the time taken by NOOP. This shows that no algorithm can be O(1/n) asymptotically, although certainly its runtime can decrease up to a limit. Commented Jul 9, 2010 at 7:25
  • 1
    Yes... as I said elsewhere, any algorithm that is O(1/n) should also take zero time for all inputs, so depending on whether you consider the null algorithm to take 0 time or not, there is an O(1/n) algorithm. So if you consider NOOP to be O(1), then there are no O(1/n) algorithms. Commented Jul 9, 2010 at 16:51
7

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).

6
  • 6
    That's not what big O is though. You can't just redefine it in order to answer the question.
    – Zifre
    Commented May 25, 2009 at 20:11
  • 11
    It's not a redefinition, it's exactly the definition of big O. Commented May 25, 2009 at 20:18
  • 10
    I am a theoretical computer scientist by trade. It's about the asymptotic order of a function.
    – Dave
    Commented May 25, 2009 at 23:03
  • 4
    Big O is a property of an arbitrary real function. Time complexity is just one of its possible applications. Space complexity (the amount of working memory an algorithm uses) is another. That the question is about O(1/n) algorithms implies that it's one of these (unless there's another that applies to algorithms that I don't know about). Other applications include orders of population growth, e.g. in Conway's Life. See also en.wikipedia.org/wiki/Big_O_notation
    – Stewart
    Commented Aug 17, 2009 at 15:51
  • 5
    @Dave: The question wasn't whether there exist O(1/n) functions, which obviously do exist. Rather, it was whether there exist O(1/n) algorithms, which (with the possible exception of the null function) can't exist
    – Casebash
    Commented Jul 9, 2010 at 10:58
6

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

4

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.

2

I believe quantum algorithms can do multiple computations "at once" via superposition...

I doubt this is a useful answer.

6
  • 1
    That would still be constant time, i.e. O(1), meaning it takes the same amount of time to run for data of size n as it does for data of size 1.
    – freespace
    Commented May 25, 2009 at 6:22
  • 2
    But what if the problem was a pale ale? (ah. hah. ha.) Commented May 25, 2009 at 6:31
  • 7
    That would be a super position to be in. Commented May 25, 2009 at 7:27
  • 2
    Quantum algorithms can do multiple computations, but you can only retrieve the result of one computation, and you can't choose which result to get. Thankfully, you can also do operations on a quantum register as a whole (for example, QFT) so you're much likelier to find something :)
    – Gracenotes
    Commented May 25, 2009 at 8:02
  • 2
    it's perhaps not useful, but it has the advantage of being true, which puts it above some of the more highly voted answers B-) Commented Jul 9, 2010 at 19:20
2

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.

2

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.

1
  • Yes, but the number of bittorrent nodes is more like the number of processors in a parallel computer. The "N" in this case would be the size of the file trying to be downloaded. Just as you could find an element in an unsorted array of length N in constant time if you had N computers, you could download a file of Size N in constant time if you had N computers trying to send you the data.
    – Kibbee
    Commented May 25, 2009 at 14:54
2

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.

4
  • 1
    Not sure I understand. Log(N) is less than N. Does that mean that Log(N) is a sublinear algorithm? And many Log(N) algorithms do exist. One such example is finding a value in a binary tree. However, these are still different than 1/N, Since Log(N) is always increasing, while 1/n is a decreasing function.
    – Kibbee
    Commented May 25, 2009 at 14:41
  • Looking at definition, sublinear time algorithm is any algorithm whose time grows slower than size N. So that includes logarithmic time algorithm, which is Log(N). Commented May 26, 2009 at 2:08
  • 2
    Uh, sublinear time algorithms can give exact answers, e.g. binary search in an ordered array on a RAM machine.
    – A. Rex
    Commented May 28, 2009 at 0:39
  • @A. Rex: Hao Wooi Lim said "In some problems".
    – LarsH
    Commented Sep 29, 2010 at 5:41
2

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.

1
  • "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." Uh... what about 1/n, or 1/n², or 1/n³, or...
    – A.P.
    Commented Oct 16, 2020 at 19:58
1

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.

4
  • i think you dont understand the meaning of O(n) Commented May 25, 2009 at 6:40
  • Not with list though, with array or hash where constains is O(1)
    – vava
    Commented May 25, 2009 at 6:43
  • ok, the random function can be thought of as a lazy array, so you're basically searching each element in the "lazy random list" and checking whether it's contained in the input list. I think this is worse than linear, not better.
    – hasen
    Commented May 25, 2009 at 6:54
  • He's got some point if you notice that int has limited set of values. So when l would contain 2<sup>64</sup> values it's going to be instantaneous all the way. Which makes it worse than O(1) anyway :)
    – vava
    Commented May 25, 2009 at 7:01
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.

1
  • 1
    "O(1/n) is not less then O(1)" -- if a function f is O(1/n), it's also O(1). And big-oh feels a lot like a "lesser than" relation: it's reflexive, it's transitive, and if we have symmetry between f and g the two are equivalent, where big-theta is our equivalence relation. ISTR "real" ordering relations requiring a <= b and b <= a to imply a = b, though, and netcraft^W wikipedia confirms it. So in a sense, it's fair to say that indeed O(1/n) is "less than" O(1). Commented May 26, 2009 at 3:15
1

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).

1

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)

0

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.

3
  • 4
    It's different kind of n in the O(n) then. With this trick you could say every algorithm has O(q) where q is number of people living in China for example.
    – vava
    Commented May 25, 2009 at 6:35
  • 2
    Boyer-Moore is of a similar kind (O(n/m)), but that's not really "better than O(1)", because n >= m. I think the same is true for your "unvisitable TSP".
    – Niki
    Commented May 25, 2009 at 6:39
  • Even in this case the runtime of the TSP is NP-Complete, you're simply removing nodes from the graph, and therefore effectively decreasing n.
    – Ed James
    Commented May 25, 2009 at 12:41
0

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.

0

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
    }
}
3
  • do you really mean sub-constant, or sublinear? Why should approximation algorithms be sub-constant? And what does that even mean??
    – LarsH
    Commented Sep 29, 2010 at 5:45
  • @LarsH, the error of approximation algorithms is proportional to the step size (or to a positive power of it), so the smaller your step size, the smaller the error. But another common way to examine an approximation problem is the error as compared to how many times an interval is divided. The number of partitions of an interval is inversely proportional to the step size, so the error is inversely proportional to some positive power of the number of partitions - as you increase the number of partitions, your error decreases.
    – Andrew Lei
    Commented Sep 2, 2017 at 2:22
  • @AndrewLei: Wow, an answer almost 7 years later! I understand Sam's answer now better than I did then. Thanks for responding.
    – LarsH
    Commented Sep 2, 2017 at 2:32
0

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.

  • Each element is more known if another element can assert its state.
  • Known elements increase the probability of asserting the state of unknown elements.

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.

Notes:

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.

9
  • 1
    You probably need O(1) time just to generate and return back a trivial answer.
    – Sebastian
    Commented Aug 31, 2023 at 3:59
  • @Sebastian It's not a trivial answer. Axioms are self-evidently true, and for an infinite N, it returns a self-evident answer. So, no you don't need O(1) to generate or return anything that is already presupposed by the algorithm. Commented Aug 31, 2023 at 20:10
  • Whether you have to generate an answer and use computation time depends on the task to solve by the algorithm and the computation model, e.g. Turing machine or whatever, and how you count the time steps. Let us assume the time steps are integers, as is the case for most theoretical computing models. An algorithm needing 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).
    – Sebastian
    Commented Sep 1, 2023 at 5:58
  • Let us assume as you've said: Suppose a computation step must be an integer in time. I already described what a supposed 1 step algorithm would be, which in this case, is discovery. However, you don't need to discover something that is already discovered which puts the step at 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
  • The algorithm doesn't care if you actually recognize the state of the elements. The algorithm has already made a decision based on the state of all pre existing elements. As observers, we can assume a state in between 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
-1
inline void O0Algorithm() {}
7
  • 1
    That would be an O(1) algorithm. Commented Jan 23, 2010 at 23:54
  • 3
    That as well, but the point is that it isn't Ω(1). And why has my answer been downrated? If you think I'm wrong, how about explaining?
    – Stewart
    Commented Feb 16, 2010 at 13:55
  • I asked elsewhere if, basically, this very answer is correct or not, and it seems to be disputed: stackoverflow.com/questions/3209139/…
    – jyoungdev
    Commented Jul 11, 2010 at 14:48
  • 1
    @StefanReich True, it isn't a very interesting answer, but it's an answer.
    – Stewart
    Commented Jun 13, 2019 at 14:13
  • 1
    @StefanReich Wrong, because O(0) is a subset of O(1/n). Maybe you're confusing O with Θ?
    – Stewart
    Commented Jun 17, 2019 at 14:16
-1

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).

1
  • Your loop requires a check which takes at least constant time, so the resulting algorithm has at least complexity O(1). Commented Jun 10, 2019 at 13:01
-1

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.

1
  • There is no such rule of Big O notation. By your logic, there could be no O(1) or O(n^2) algorithms, for example. Commented Apr 17, 2023 at 18:08
-2

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)

2
  • Really? You would still need to return a value, so wouldn't it still be O(1)? Commented May 25, 2009 at 8:51
  • 7
    no, O(0) would imply it takes zero time for all inputs. O(1) is constant time. Commented May 25, 2009 at 8:51
-2

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)

5
  • No: Big O notation is also used to talk about average-case and expected time (and even best-case) scenarios. The rest follows. Commented May 25, 2009 at 13:23
  • The 'O' notation certainly defines an upper bound (in terms of algorithmic complexity, this would be the worst case). Omega and Theta are used to denote best and average case, respectively. Commented May 25, 2009 at 13:59
  • 2
    Roland: That's a misconception; upper bound is not the same thing as worst-case, the two are independent concepts. Consider the expected (and average) runtime of the 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
  • Konrad: True. Still, Omega, Theata and O are usually used to express bounds, and if all possible inputs are considered, O represents the upper bound, etc. Commented May 25, 2009 at 15:03
  • 1
    The fact that O(1/n) is a subset of O(1) is trivial and follows directly from the definition. In fact, if a function g is O(h), then any function f which is O(g) is also O(h).
    – Tobias
    Commented Jun 11, 2009 at 17:43
-2

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

-2

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).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.