Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
3  
$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$. –  A.Schulz Jan 17 '13 at 18:50
add comment

1 Answer 1

up vote 8 down vote accepted

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

share|improve this answer
    
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})$. –  Imray Jan 17 '13 at 20:04
1  
@lmray -- yep, absolutely. I hope what I wrote was helpful too. –  usul Jan 17 '13 at 21:14
3  
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))$. –  Yuval Filmus Jan 18 '13 at 3:08
    
@Yuval good point, let me add that to the answer as a postscript. Of course that's assuming the algorithm halts on all inputs. –  usul Jan 18 '13 at 5:11
    
Very clear now, thanks! –  Imray Jan 22 '13 at 15:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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