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
Why we write
1 inside the
What does the
1 mean? Why not
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.
O(34 * n^2) = O(1 * n^2) = O(n^2)
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) ...
This is all very hand-wavy, but there is a mathematical reason why we don't use Theta(c) and instead use Theta(1). I'll use Big O notation instead to show this.
It has to do with a property of Big Theta (as well as Big O and Big Omega) notation. If you have a function with growth rate
O(g(x)) and another with growth rate
O(c * g(x)) where
c is some constant, you would say they have the same growth rate. That is
O(c * g(x)) = O(g(x))
We can say this because the definition of Big O notation (
f(x) = O(g(x))) means that we have a function
f(x) and function
g(x) such that
|f(x)| <= k * |g(x)| for some constant
k and large enough values of
x. When multiplying by the constant
c, we would then have:
O(c * g(x)) => k * |c * g(x)| = k * |c| * |g(x)| <= k' * g(x) where
k' = k * |c|
|k' * g(x)| <= k'' g(x) for some constant
k'' and large enough values of
x, which means
k' * g(x) grows at a rate of
O(g(x)) and therefore
O(c * g(x)) = O(g(x))
g(x) = 1, we have
O(1) growth, saying
O(c) growth for some value of
c doesn't tell us anything because the constant is already factored in to the definition of Big O notation. Simplified
O(c) = O(1)
Well, of course you could write Theta(c) (or O(c)) but why does that differ from Theta(n)? n is just a variable that denotes the size of the input. You could write "The function is Theta(c) where c is a constant". The important addendum is ...where c is a constant. You have to explicitly state that an identifier is not a variable.
Consider graph theory where the bounds for an algorithm is often described as a function of |V| and |E|, or the node and edge count, respectively. Then it might be prudent to state "The function is Theta(|V| * |E|^2)".
Theta(1) however is always a constant - assuming normal mathematical practices.
O(c) specifically means that the associated class of algorithms grows linearly with c, where c is the size of an input to the algorithm or a parameter to the algorithm. It isn't the same c that is used to explain O-notation, because that c is only relevant to the explanation, not the usage. O(c) contains a different c that must come from the algorithm input context.