9

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.

Johan
  • 74,508
  • 24
  • 191
  • 319
Barak Aburus
  • 115
  • 1
  • 1
  • 8
  • I have often seen in CLRS texts that the authors use O(1) for a constant statement instead of Theta(1). Well the book is very specific though. One reason for using big-oh for a statement requiring constant time to execute is, people are more concerned about worst case scenario which is reflected by the big-oh notation... But a statement requiring constant time for execution could indeed contribute O(1) to the total execution time instead of Theta (1) if the statement is conditionally executed. Hence it has no guarantee of execution an hence its cost is not lower bounded by 1. – Abhishek Ghosh Aug 07 '21 at 18:33

2 Answers2

8

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!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
0

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).

Stuart Golodetz
  • 20,238
  • 4
  • 51
  • 80
  • 1
    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? – Barak Aburus Sep 07 '13 at 20:34
  • There's no distinction when talking about constant time, because the lower bound is implied. But see here for an interesting discussion: http://stackoverflow.com/questions/905551/are-there-any-o1-n-algorithms – Stuart Golodetz Sep 07 '13 at 20:42
  • 1
    Are you sure about this? My answer has what I believe is a counterexample in it. – templatetypedef Sep 15 '13 at 23:06
  • 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. – mazunki Mar 18 '21 at 04:42
  • 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: https://stackoverflow.com/questions/1286364/is-it-ever-possible-to-have-big-o-less-than-o1 – Stuart Golodetz Mar 18 '21 at 13:37
  • @mazunki By the way, see also the definition of Big Theta given here: https://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). – Stuart Golodetz Mar 18 '21 at 14:10
  • 1
    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. – mazunki Mar 18 '21 at 14:37