Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

share|improve this question

5 Answers 5

up vote 7 down vote accepted

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

share|improve this answer
    
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

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)

share|improve this answer

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.

share|improve this answer
    
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
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

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

share|improve this answer
    
But why do you say n^0 to denote constant time and not n^1 in your example? –  user10326 Sep 24 '11 at 17:02
    
@user10326, because n^1 = n is not constant. It grows linearly. –  Peter Taylor Sep 24 '11 at 19:45

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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