Why Use 1 in Theta Notation for Constant Time?

algorithmsbig-theta

In asymptotic notation when it is stated that if the problem size is small enough (e.g. n<c for some constant c) the solution takes constant time and is writen as Theta(1).
Why we write 1 inside the Theta?
What does the 1 mean? Why not Theta(c)?

Best Answer

Those notations are meant to denote the asymptotic growth. Constants do not grow and thus it's pretty equal which constant you choose. However, there's a convention that you choose 1 to indicate no growth.

I assume that this is due to the fact that you want to simplify the mathematical terms in question. When you've got a constant factor just divide by it and all that's left of it is 1. This makes comparisons easier.

Example:

O(34 * n^2) = O(1 * n^2) = O(n^2)

and

O(2567.2343 * n^2 / 5) = O(n^2)

See what I mean? As these mathematical terms get more and more complicated, you don't want to have noisy constants when they're not relevant for the information you're interested in. Why should I write O(2342.4534675767) when it can be easier expressed with O(1), which communicates the facts of the case unambiguously.

Further, the wikipedia article about time complexity also implies it's a convention:

An algorithm is said to be constant time (also written as O(1) time) ...