What is the difference between O(1) and Θ(1)?

10,338

Solution 1

Big-O notation expresses an asymptotic upper bound, whereas Big-Theta notation additionally expresses an asymptotic lower bound. Often, the upper bound is what people are interested in, so they write O(something), even when Theta(something) would also be true. For example, if you wanted to count the number of things that are equal to x in an unsorted list, you might say that it can be done in linear time and is O(n), because what matters to you is that it won't take any longer than that. However, it would also be true that it's Omega(n) and therefore Theta(n), since you have to examine all of the elements in the list - it can't be done in sub-linear time.

UPDATE:

Formally:

  • f in O(g) iff there exists a c and an n0 such that for all n > n0, f(n) <= c * g(n).

  • f in Omega(g) iff there exists a c and an n0 such that for all n > n0, f(n) >= c * g(n).

  • f in Theta(g) iff f in O(g) and f in Omega(g), i.e. iff there exist a c1, a c2 and an n0 such that for all n > n0, c1 * g(n) <= f(n) <= c2 * g(n).

Solution 2

O(1) and Θ(1) aren't necessarily the same if you are talking about functions over real numbers. For example, consider the function f(n) = 1/n. This function is O(1) because for any n ≥ 1, f(n) ≤ 1. However, it is not Θ(1) for the following reason: one definition of f(n) = Θ(g(n)) is that the limit of |f(n) / g(n)| as n goes to infinity is some finite value L satisfying 0 < L. Plugging in f(n) = 1/n and g(n) = 1, we take the limit of |1/n| as n goes to infinity and get that it's 0. Therefore, f(n) ≠ Θ(1).

Hope this helps!

Share:
10,338
Barak Aburus
Author by

Barak Aburus

Updated on June 23, 2022

Comments

  • Barak Aburus
    Barak Aburus over 1 year

    I know the definitions of both of them, but what is the reason sometimes I see O(1) and other times Θ(1) written in textbooks?

    Thanks.

  • Barak Aburus
    Barak Aburus about 10 years
    is there a difference between them when talking about a constant? also is there a case that there will be a requirement for Theta 1 and not O 1?
  • Stuart Golodetz
    Stuart Golodetz about 10 years
    There's no distinction when talking about constant time, because the lower bound is implied. But see here for an interesting discussion: stackoverflow.com/questions/905551/…
  • templatetypedef
    templatetypedef about 10 years
    Are you sure about this? My answer has what I believe is a counterexample in it.
  • mazunki
    mazunki over 2 years
    This answer is not correct, and shouldn't be marked as such. It's spreading misinformation. Big-Theta represents the average time for large n (ish), and has nothing to do with lower bound. The lower bound is defined by Big-Omega.
  • Stuart Golodetz
    Stuart Golodetz over 2 years
    To the best of my knowledge, the answer I originally gave is, in and of itself, correct (see update), and I think your comment may be incorrect (again, see update). The comment I made that @templatetypedef challenged I'm less confident about. I think I want to stand by it in the context of running an algorithm on a computer (in that I don't know of any algorithms that take less than constant time), but I think I buy templatetypedef's answer more generally. See also: stackoverflow.com/questions/1286364/…
  • Stuart Golodetz
    Stuart Golodetz over 2 years
    @mazunki By the way, see also the definition of Big Theta given here: en.wikipedia.org/wiki/Big_O_notation. Note that I didn't say "Big Theta notation expresses an asymptotic lower bound", I said "Big Theta notation additionally expresses an asymptotic lower bound". That's true, in the sense that if something is Theta(n) then it's O(n) and Omega(n), so Theta(n) not only expresses O(n), it also expresses Omega(n).
  • mazunki
    mazunki over 2 years
    I must have entirely skipped the "additionally" part while reading this earlier. I retire what I said, since Θ(f) does indeed represent a sandwich, and not only a ceiling or floor.