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

Question

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

Thanks.

Answer 1

The Big-O designation expresses an asymptotic upper bound, while the Big-Theta notation additionally expresses an asymptotic lower bound. Often the upper bound is what interests people, so they write O (something), even when Theta (something) is also true. For example, if you want to count the number of things equal to x in an unsorted list, you can say that this can be done in linear time and there is O (n), because for you it is important, t take more than that. However, it would also be true that this is Omega (n) and therefore Theta (n), since you need to examine all the elements in the list - this cannot be done in sublinear time.

Answer 2

O (1) and? Theta; (1) do not necessarily match 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 & Theta; (1) for the following reason: one definition of f (n) = & Theta; (g (n)) is that the limit | f (n) / g (n) | when n goes to infinity, there is some finite value of L satisfying 0 <L. Taking f (n) = 1 / n and g (n) = 1, we take the limit | 1 / n | since n goes to infinity and gets this value 0. Therefore, f (n) ≠ & Theta; (1).

Hope this helps!