From what I've read, Big O is the absolute worst ever amount of complexity an algorithm will be given an input. On the side, Big Omega is the best possible efficiency, i.e. lowest complexity.

Can it be said then that every algorithm has a complexity of $O(\infty)$ since infinite complexity is the worst ever possible? By the same token, can it be said that every algorithm is $\Omega(1)$ since the absolute lowest complexity an algorithm can be is a constant?

  • 4
    $\begingroup$ $O(\infty)$ doesn't make sense, since it has to be $O(f(n))$, for $f(n)$ being a (total) function, and $\infty$ is not a function. Notice that in $O(1)$, the 1 is just a shortcut notation for the function $f\equiv 1$. $\endgroup$
    – A.Schulz
    Jan 17, 2013 at 18:50

1 Answer 1


To be clear, Big O and Big Omega are classes of functions. So if I have for example $\Omega(1)$, that's a set of a whole bunch of functions.

An algorithm's complexity is a function giving how many steps the algorithm takes on each input. This function may be in a class like $\Omega(1)$, or not.

$\Omega(1)$ is the class of functions $f(x)$ that are greater than some constant $c$ as $x$ goes to infinity. According to the technical definition, the function $f(x) = 0$ is not $\Omega(1)$, so an algorithm that never takes any steps (for instance) would not have complexity $\Omega(1)$. But virtually all algorithms would have complexity in $\Omega(1)$. (For example algorithms that always take at least one step.)

Since $\infty$ is not a number, $O(\infty)$ is not defined under any definition I've seen. It does not seem to be interesting to make this definition ( "all functions which are either finite or undefined"? but that is just all functions). So intuitively the answer to your question is yes, infinity is an upper bound on all algorithms' running times, but technically it's somewhat meaningless.

As a sidenote, we could extend little-o to include a domain of infinity by saying $f(x)$ is $o(\infty)$ if $f(x)$ is finite (i.e. well-defined) for all $x$. Under a definition like that, an algorithm that does not halt on some inputs would not have complexity $o(\infty)$. But every algorithm that does halt on all inputs would.

Edit/PS as pointed out by Yuval, we can give a slightly better answer for $O(\infty)$. Let's restrict attention to algorithms that halt on all inputs. Then we can define a function that grows like the maximum number of steps taken by any algorithm that halts. Call it $B(n)$. Then every algorithm's running time will be $O(B(n))$.

To define the function, let's take Yuval's suggestion and let $B(n) = $ the maximum number of steps taken by any halting TM of up to $n$ states on an input of up to $n$ bits. Now given any algorithm, it will be encoded as a Turing Machine, so it will have a certain number of states; say $N$ of them. Then the running time of the algorithm on inputs of size $m \geq N$ is at most $B(m)$. We can see this because $B(m)$ takes the maximum over all Turing Machines up to a certain size, including this one, so $B(m)$ will be at least as big as this TM's runtime.

See also: http://en.wikipedia.org/wiki/Busy_beaver

  • $\begingroup$ Thanks for that explanation. What I was getting at was that if you have a simple function with one for loop, you can probably safely say that it is $O(n^{1000n})$. $\endgroup$ Jan 17, 2013 at 20:04
  • 1
    $\begingroup$ @lmray -- yep, absolutely. I hope what I wrote was helpful too. $\endgroup$
    – usul
    Jan 17, 2013 at 21:14
  • 4
    $\begingroup$ Let $f(n)$ be the maximal number of steps taken by a halting TM having up to $n$ states on any input of up to $n$ bits. Then every algorithm is $O(f(n))$. $\endgroup$ Jan 18, 2013 at 3:08
  • $\begingroup$ @Yuval good point, let me add that to the answer as a postscript. Of course that's assuming the algorithm halts on all inputs. $\endgroup$
    – usul
    Jan 18, 2013 at 5:11

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.