9

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

5 Answers 5

9

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

5
  • I see.But why not just Theta(c) to cover any constant?It is just a convention?
    – user10326
    Sep 24, 2011 at 13:56
  • 8
    @user10326: I think it's because "c" could be misinterpreted, you clearly have to state that it is a constant while "1" does the same job unambiguously.
    – Falcon
    Sep 24, 2011 at 13:58
  • So the actual number is irrelevant?We use 1 instead of 5 as a convention?
    – user10326
    Sep 24, 2011 at 14:54
  • 1
    @user10326: Yes, because it doesn't make a difference. But I'd refrain from using "0" because that could lead to a lot of confusion.
    – Falcon
    Sep 24, 2011 at 15:09
  • @user10326: Falcon his answer made perfect sense didn't it? if it would be 5 instead of 1, dropping 5 in O(5 * n^2) would feel less natural, while dropping * 1 is basic math. Sep 24, 2011 at 15:50
13

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|

Note that |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))

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

3

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.

6
  • Theta(1) however is always a constant.This is the part I do not get.Theta(c) is always a constant as well.Right?So I was wondering if the 1 has a special meaning
    – user10326
    Sep 24, 2011 at 13:58
  • 5
    @user10326: no, c is not always a constant, since c is a variable if you do not explicitly state that it should be in fact interpreted as a constant... Which is exactly the subtle difference that is avoided by 1.
    – blubb
    Sep 24, 2011 at 14:09
  • Ok, but it represents a constant time.
    – user10326
    Sep 24, 2011 at 14:19
  • 2
    @user10326: No, no, it does not represent a constant time. It represents time that grows linearly with c. Those are different, because you need something additional to force the value of c to never change, whereas 1 never changes.
    – jprete
    Sep 24, 2011 at 17:13
  • 1
    @user10326: Or, put more simply: c isn't a constant; c is a letter. Other letters represent variables, how do you expect the reader to know this one doesn't as well?
    – Random832
    Sep 24, 2011 at 18:38
0

Theta notation is about growth as a function of some variable - typically n. If it were necessary to clarify which variable is intended, the way to write it would be Theta(n^0). From there it's a simple step to apply the identity n^0 = 1 (for n != 0).

2
  • But why do you say n^0 to denote constant time and not n^1 in your example?
    – user10326
    Sep 24, 2011 at 17:02
  • @user10326, because n^1 = n is not constant. It grows linearly. Sep 24, 2011 at 19:45
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.