Constant time is the absolute low end of time complexity. One may wonder: is there anything nontrivial that can be computed in constant time? If we stick to the Turing machine model, then not much can be done, since the answer can only depend on a constant length initial segment of the input, as farther parts of the input cannot even be reached in constant time.
On the other hand, if we adopt the somewhat more powerful (and more realistic) unit-cost RAM model, in which elementary operations on $O(\log n)$-bit numbers are counted as single steps, then we may be able to solve nontrivial tasks, even in constant time. Here is an example:
Instance: Integers $n, k, l, d$, each given in binary format by $O(\log n)$ bits.
Question: Does there exist an $n$-vertex graph, such that its vertex connectivity is $k$, its edge connectivity is $l$, and its minimum degree is $d$?
Note that from the definition it is not even obvious that the problem is in NP. The reason is that the natural witness (the graph) may need $\Omega(n^2)$-bit long description, while the input is given by only $O(\log n)$ bits. On the other hand, the following theorem (see Extremal Graph Theory by B. Bollobas) comes to the rescue.
Theorem: Let $n, k, l, d$ be integers. There exists an $n$-vertex graph with vertex connectivity $k$, edge connectivity $l$, and minimum degree $d$, if and only if one of the following conditions is satisfied:
- $0\leq k\leq l \leq d <\lfloor n/2 \rfloor$,
- $1\leq 2d+2-n\leq k\leq l = d< n-1$
Since these conditions can be checked in constant time (in the unit-cost RAM model), the Theorem leads to a constant time algorithm in this model.
Question: What are some other nontrivial examples of constant time algorithms?