3
$\begingroup$

When can an algorithm be said to have $O(1)$ complexity? My doubt is if $n$ is specified to be a large number but constant and we cannot implement it in reality without a loop even then can we call it to have $O(1)$ time complexity? Consider the following examples.

  1. Algorithm to add first 1000 natural numbers (that is I mean to say if n is specified directly). Then can we say this has $O(1)$ time complexity?

  2. Finding the $7$th smallest element in a min heap. This element is present in anywhere in the first 6 levels of the heap (considering root at level 0). So to find the element we need to check $2^7 - 1$ elements. Then can we say this has $O(1)$ time complexity?

$\endgroup$
  • 1
    $\begingroup$ I'm not aware of an algorithm that needs to process input of variable length that has $\mathcal{O}(1)$ time complexity. On the other hand, an algorithm that does the same thing regardless of its input, if it terminates, always has $\mathcal{O}(1)$ time complexity. What is rather common are data structures that already preprocessed the input where we can have operations with constant time complexity. $\endgroup$ – G. Bach Nov 28 '13 at 19:29
  • 1
    $\begingroup$ Getting the first element of a list is O(1) (regardless of the size of the list). $\endgroup$ – Dave Clarke Nov 28 '13 at 20:04
  • $\begingroup$ @Dave But it always terminates in $\mathcal{O}(1)$ time and Bach's statement is still true. $\endgroup$ – Parham Nov 28 '13 at 23:38
  • $\begingroup$ this problem actually depends on how the TM setup to the problem is defined because if the TM head starts on the end of the input it takes $O(n)$ just to get to the start of the input.... as I understood from another question $O(n)$ for functions smaller than $n$ is not really defined... $\endgroup$ – vzn Dec 1 '13 at 1:53
  • 1
    $\begingroup$ An algorithm never has a "complexity". That's for problems. Algorithms have runtimes, and runtime functions have asymptotics. $\endgroup$ – Raphael Dec 2 '13 at 12:21
2
$\begingroup$

If you follow the definition of $\mathcal O$, a function $f(x)\in\mathcal O(1)$ when there's an $x_0$ and $M$ such that for all $x>x_0$, $f(x) \leq M$.

For both algorithms you mention, there clearly is an upper bound on the number of steps a machine has to take to compute the result. Therefore, the time complexity for either problem will be some function $T(n)$, where $n$ is the length of the input, such that $T(n)\leq M$ for some $M$ for all $n$. Therefore $T(n)\in \mathcal O(1)$.

Note that the $\mathcal O$ notation has to do with asymptotic behavior of functions, i.e. their behavior as their input grows beyond all bounds. It doesn't care about tiny inputs, whether their length is $1$, $2^7$, or $10^{100}$.

$\endgroup$
1
$\begingroup$

Remeber that, in complexity theory, "$n$" is the length of the input to the problem, in bits.

In your first example, the machine just writes "500500" to its output tape (or "1111010001100010100", if you prefer to work in binary), which takes 6 (or 19) steps, which is $O(1)$. This problem has no input so it doesn't make sense to talk about $n$.

In your second example, you only need to check a constant number $c$ of entries in the heap. But what's your input? How is it represented? What model of computation are you using? Presumably, the input (which, remember, has $n$ bits) is the whole heap, containing $k$ entries. Therefore, each entry takes about $n/k$ bits. On a Turing machine, you're going to have to scan at least $cn/k$ tape cells, so your complexity is $\Theta(n)$. On a random access machine, the time complexity will depend on your data representation but it's probably still going to be $\Theta(n)$.

$\endgroup$
0
$\begingroup$

There is something tricky about this question. The answer for whether an algorithm runs in constant time depends on how large the input to the algorithm is (in bits). In practice we usually assume the size is small enough so that it fits in the memory of our physical random access machine and also each basic operation is performed in constant time.

But in theory the input size can be arbitrarily large and complexity results are the same on both RAM and Turing machine. However, working with a TM is more convenient.

The first example is always of constant size because the input size is zero (notice that 1000 cannot be the input). On the contrary the second example would not be of constant time if the input size is not a constant (this is the answer to your first question). Suppose the heap contains $m$ elements, each encoded in at least $\log m$ bits (under a reasonable encoding). A simple operation like comparison takes $\theta(\log m)$ time. So it has $\theta(2^7.\log m)$ time complexity to find the first 7 smallest elements.

Similarly, the first example wouldn't be of constant time if it was "Algorithm to add first 1000 numbers in a given list of $n$ natural numbers".

$\endgroup$
  • $\begingroup$ In the random access machine model, the memory is unbounded. It doesn't make sense to say "assume the size is small enough so that it fits in the memory" because any finite amount of data fits in the memory. $\endgroup$ – David Richerby Nov 29 '13 at 23:04
  • $\begingroup$ Yes, you're right. I tried to mean a physical machine not an abstract one. $\endgroup$ – Parham Nov 30 '13 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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