-3
$\begingroup$

I am a CS first year student, and as I was reviewing over the theta notation unit, I saw that $\Theta(1)$ exists. I was wondering if there was any real life example algorithm that has a running time of $\Theta(1)$.

$\endgroup$
1
  • 1
    $\begingroup$ What is a "real life algorithm"? Here is an algorithm: ignore the input, and print "yes". $\endgroup$ – Bader Abu Radi Jan 17 at 15:33
2
$\begingroup$

You talk about "real-life example", which is not really well defined. I take it to mean that you want an example of some "standard" algorithm that is studied in computer science and not something made up with the sole purpose of running in time $\Theta(1)$.

If you are fine looking at the complexity of algorithms that implement some data structure operation then there are several examples:

  • A tree can be preprocessed in linear time so that, given any two vertices, their LCA can be found in $\Theta(1)$ time.

  • A tree can be preprocessed in linear time so that, given a vertex $u$ and an integer $\ell$, the ancestor of $u$ at depth $\ell$ can be returned in $\Theta(1)$ time.

  • Two Fibonacci heaps can be combined into a single Fibonacci heap in $\Theta(1)$ time.

  • Inserting an element and decreasing the key of an element in a strict Fibonacci heap both take $\Theta(1)$ time.

  • Any array $A[1, \dots, n]$ can be preprocessed in linear time so that, given two indices $i,j$, the quantity $\min_{i \le k \le j} A[k]$ can be returned in $\Theta(1)$ time.

  • Under reasonable assumptions, given a discrete probability distribution over a set $S$ of $n$ elements, it is possible to preprocess $S$ so that an element from $S$ can be sampled in $\Theta(1)$ time (according to the distribution).

  • ...

$\endgroup$
2
$\begingroup$

Real-life algorithms with $\Theta(1)$ exist. Consider the problem of, given an array $A$ of $n$ integers of $O(\log{n})$ bits each and two integers $1\leq i,j\leq n$, computing $A[i]+A[j]$. This problem has a $\Theta(1)$ algorithm.

Of course, any problem with a $\Theta(1)$ algorithm is exceedingly simple.

$\endgroup$
2
  • $\begingroup$ If you are looking at bit wise complexity then the addition operation has $\Theta(\log n)$ complexity, and not $\Theta(1)$. Check this link: cs.stackexchange.com/questions/1643/… $\endgroup$ – Inuyasha Yagami Jan 17 at 13:39
  • 1
    $\begingroup$ Clearly, the complexity of addition in the logarithmic costs model is the $O(\log M)$ where $M$ is the maximum (absolute value) of the two operands. Tom van der Zanden was implicitly using the word-RAM model with the assumption that each integer (i..e, array entry) fits into a word of memory. This is standard. Anyway, the point remains: you can come up with algorithms that run in constant time, although most of them won't really be interesting. For example, given $i$ and $j$, report the parity of $A[i] \oplus A[j]$. $\endgroup$ – Steven Jan 17 at 17:49

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.