Why run time of the following algorithm is O(1) and not Θ(1)?

Question

Algorithm for Enqueue:

ENQUEUE(Q,x)  
1.Q[Q.tail]=x  
2.if Q.tail==Q.length  
3.    Q.tail=1  
4.else Q.tail=Q.tail+1 

It has time complexity O(1).
My question is why it is not Θ(1) ?

Answer 1

It is O(1) and Θ(1). (unless the x or Q.length has infinite bits.)

---

O(1) means that the algorithm has a time complexity of at most a constant. It's the upper bounds.

For your case, let's say the algorithm takes a time t to insert x into a fixed address(Q.tail), and then increase the address by 1. It's easy to see that t doesn't increase depending on whatever the n or Q is, and t can't be infinity. So the upper bound of this algorithm is O(1), because:

And, It's easy to see that no matter what the n or Q is, t must be longer than a constant time to let the machine work. t could not be infinitesimal. So the lower bound of this algorithm is Ω(1). it means that the algorithm has a time complexity of at least a constant.

Finally, it's a definition that if T(F(n)) = O(1) and T(F(n)) = Ω(1), then T(F(n)) = Θ(1). (If you forget it, please go through the first chapter of the Introduction to Algorithm.)