12
$\begingroup$

Does saying $f(x) = \Theta(1)$ provide any extra information over saying $f(x) = O(1)$?

Intuitively, nothing grows more slowly than a constant, so there should be no extra information in specifying Big Theta over Big O in this case.

$\endgroup$
  • 1
    $\begingroup$ In a sentence: It doesn't make sense for describing execution time or similar functions, but does make sense for describing how close to zero a function might get. $\Theta(1)$ means "doesn't drop too far beneath 1, multiplicatively". $\endgroup$ – einpoklum Mar 30 at 6:43
14
$\begingroup$

Remember your definitions! As $n \to \infty$ (the use in CS, almost always) $O(\cdot)$ is an upper bound (within a constant multiple, for large $n$), $\Omega(\cdot)$ is a lower bound (within a constant multiple, for large $n$), and $\Theta(\cdot)$ both of the previous. To see the difference, as $n \to \infty$ you have:

$\begin{align*} 1 + \lvert \sin n \rvert &= O(1) \\ 1 + \lvert \sin n \rvert &= \Omega(1) \\ 1 + \lvert \sin n \rvert &= \Theta(1) \\ e^{-n} &= O(1) \\ e^{-n} &\ne \Omega(1) \\ e^{-n} &\ne \Theta(1) \end{align*}$

For the first three, as $\sin x$ moves between -1 and 1, the expression fluctuates between 1 and 2.

To see why $e^{-n} \ne \Omega(1)$ (and so $e^{-n} \ne \Theta(1)$), note that we are looking for a constant $c > 0$ and an $N_0$ so that for all $n \ge N_0$ we have $e^{-n} \ge c \cdot 1$. For any $c$ you pick, you'll find that taking $n > \ln 1 / c$ makes this false. So no $c$ works.

| cite | improve this answer | |
$\endgroup$
  • 5
    $\begingroup$ Just adding that often times one deals with functions that are positive and monotonically non-decreasing. In that case you trivially have $f(x) = \Omega(1)$ and $f(x)=O(1)$ implies $f(x)=\Theta(1)$. $\endgroup$ – Steven Mar 29 at 3:05
  • 3
    $\begingroup$ Probably too pedantic but just to note that since we are in an unusual case for CS special care must be taken regarding the definition of $\Omega$: there are two definitions which usually coincide in CS but not always in such settings. For instance $|\sin n|=\Omega (1)$ (Hardy-Littlewood's definition) but $|\sin n|\neq \Omega (1)$ (Knuth's definition), however the functions in the answer were well chosen as $1+|\sin n|=\Omega (1)$ and $e^{-n}\neq \Omega(1)$ according to both definitions. $\endgroup$ – eru-cs Mar 29 at 9:38
  • 5
    $\begingroup$ @northerner: As far as I can tell, the question is "does $O(1)$ imply $\Theta(1)$?". vonbrand's answer is : "No. Here's a counterexample, which is $O(1)$ but not $\Theta(1)$". $\endgroup$ – Eric Duminil Mar 29 at 10:57
  • 3
    $\begingroup$ @northerner, this is not about "execution time of algorithms", that is just one use. $\endgroup$ – vonbrand Mar 29 at 13:36
  • 4
    $\begingroup$ @northerner Discrete mathematics often deals with asymptopic growths of various things (because getting an exact formula is often hard or even impossible). There, "small" terms such as $e^{-n}$ could be rolled into an $O(1)$ term to make the analysis easier. $\endgroup$ – Norrius Mar 29 at 14:01
13
$\begingroup$

vonbrand's answer is correct in general, but let me add that if $\boldsymbol{f(n)}$ is the running time of an algorithm, then you are correct, $\boldsymbol{O(1)}$ and $\boldsymbol{\Theta(1)}$ are the same. This is because running times of algorithms are positive integers, so the example $f(n) = e^{-n}$ is impossible. As you said, intuitively, nothing grows slower than a constant.

In particular, if $f$ is the running time of an algorithm, then $f(n) \ge 1$ for all $n$, because it takes at least one step for the machine to halt and return its output. From this we can deduce that $f(n) = \Omega(1)$, that is, every function grows at least as fast as a constant.

This assumes that an algorithm's running time can't be zero. If we allow that (i.e., halting doesn't count as a step), then there is exactly one algorithm that is $O(1)$ but not $\Theta(n)$ -- the "do nothing and halt" algorithm. This has running time $0$, which is $\Theta(0)$, not $\Theta(1)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ My sort routine can very well run in a fraction of a second, some algorithms do run faster for some instances of larger values. Just compare multiply by hand $12345 × 567341$ with $2000 × 60000$ for a dumb example. $\endgroup$ – vonbrand Mar 29 at 16:14
  • 4
    $\begingroup$ @vonbrand I'm not sure why that's relevant? Algorithm running time isn't measured in seconds, it's measured in steps (time in seconds depends on a lot of factors that have nothing to do with the algorithm, like processor clock speed). And it doesn't matter whether larger computations can be done in fewer steps than smaller ones: the important thing is that they always require at least one step. Therefore, there is an asymptotic lower bound on the execution time of any program: $f(n)=1$. For any program, running time $T(n) \ge f(n)$ for all $n$, so $T(n)$ is in $\Omega(1)$. $\endgroup$ – cpast Mar 29 at 17:57
  • 4
    $\begingroup$ @vonbrand Computation (at least, on digital computers as we know it today) is discrete. The only reason your sort routine runs in a non-integer value is because you've measured it in terms of seconds instead of steps. And even if you measure it in seconds, it doesn't change the fact that $O(1)$ and $\Theta(1)$ end up being the same class. $\endgroup$ – 6005 Mar 29 at 17:59
  • 3
    $\begingroup$ It might be good to note that there are other common uses of $\Theta$ and $O$ in CS for which the "positive integer" assumption does not apply. For example, in a $c$-approximation algorithm of a maximization problem, $c$ lies in $[0,1]$. (At least, according to one of the common definitions of approximation algorithms) $\endgroup$ – Discrete lizard Mar 29 at 18:06
4
$\begingroup$

The Big O notation is not only used to express algorithm complexity. It is also commonly used to express precision of approximations in mathematics. See for example the Stirling's approximation, which uses $O(1/n)$ as a term explaining how good the approximation is. Then you are not necessarily dealing only with functions that grow.

Obviously an $f(n) \in O(1/n)$ is also $O(1)$, and any $f(n) \in \Theta(1)$ is also $O(1)$, but if $f(n) \in O(1/n)$, then it's not in $\Theta(1)$.

If in your context it is clear that $f$ has a positive lower bound (e.g. $1$), then whether you use $O(1)$ or $\Theta(1)$ doesn't matter. But in general, there is a difference.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Yes, it has additional information.

Consider the following algorithm: "If input N is odd, do something that takes a constant time. If N is even, do nothing." In the odd case, this means that Big O is on the order of 1. In the even case, this means that Big Omega is on the order of 0. This, in turn, means that there is no Big Theta, because there is no function that describes both its upper and lower bounds.

This sort of situation is easier to see when you're dealing with Big O factors larger than 1: for instance, an algorithm that said "If N is odd, add all numbers between 1 and N together and return the result; if N is even, return N" would have a Big O of N and a Big Omega of 1 - and it wouldn't have a Big Theta.

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ This isn't correct because the algorithm starts by checking the parity of $N$, which takes time $\Theta(1)$ irrespective of the result. You can't have an algorithm which takes time $0$ for some inputs and not others. $\endgroup$ – Especially Lime Mar 30 at 9:51
  • $\begingroup$ Doing nothing runs in constant time as well. O(1) describes that there is a constant that is a bound of the time complexity. When you actually want to calculate the constant for your even/odd example it would be max(k_even*1, k_odd*1). k_even is 0 and k_odd is some constant value greater than 0. So the k of O(1) would be k_odd. But for the Big-O notation it only matters, that a constant exists, such that k that is an upper bound for all possible inputs. $\endgroup$ – allo Mar 30 at 13:21
-4
$\begingroup$

I went and looked it up for this question. "Big Theta" and "Big O" are defined slightly differently, but then found that "Big O" has different definitions depending on where you look.

Depending on who you ask, you can have an amortized "Big O" resulting in O(1) where every n operations, it would have to run a linear step rather than a constant and still label it O(1). We did it this way when I was in college. More information here: https://stackoverflow.com/questions/200384/constant-amortized-time

"Big Theta" is more precise in that everybody agrees on its definition in that such steps are not allowed.

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ This is not accurate. "amortized" vs. "worst-case" are ways to calculate the running time of an algorithm; they aren't part of the definition of Big O and Big Theta. Big O of a function like $f(n)$ is defined mathematically, and it's the same whether $f(n)$ denotes amortized time, worst-case time, or the number of penguins in my bathtub at time $n$. There's no disagreement in the definition. $\endgroup$ – 6005 Mar 29 at 17:57

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.