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

Thomas Owens
  • 79,623
  • 18
  • 192
  • 283
user10326
  • 1,834
  • 3
  • 17
  • 18

5 Answers5

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)

Jay Lindquist
  • 618
  • 4
  • 10
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) ...

Falcon
  • 19,248
  • 4
  • 78
  • 93
  • I see.But why not just Theta(c) to cover any constant?It is just a convention? – user10326 Sep 24 '11 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 '11 at 13:58
  • So the actual number is irrelevant?We use 1 instead of 5 as a convention? – user10326 Sep 24 '11 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 '11 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. – Steven Jeuris Sep 24 '11 at 15:50
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.

Max
  • 2,039
  • 1
  • 16
  • 22
  • `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 '11 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 '11 at 14:09
  • Ok, but it represents a constant time. – user10326 Sep 24 '11 at 14:19
  • @user10326 Well the convention is to use n as a variable. c is oftentimes used as a constant, but to avoid any disambiguity an explicit constant in chosen - 1. While that is also a bit confusing (since 1 is usually not the correct constant) it essentially behaves as any other constant (not affected by any variables) – Max Sep 24 '11 at 15:29
  • 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 '11 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 '11 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).

Peter Taylor
  • 4,012
  • 1
  • 24
  • 29
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.

jprete
  • 1,509
  • 11
  • 16