# Value of constants in Big Theta notation

In Big Theta notation used for defining the running time of an algorithm, are the constants $c_1$ and $c_2$ different for every value of $n$?

Definition:

$\qquad \displaystyle \Theta (g(n)) = \{ f(n): \exists\, c_1,c_2,n_0>0. \forall n \geq n_0.\ \ c_1g(n) \leq f(n) \leq c_2g(n) \}.$

## migrated from cstheory.stackexchange.comSep 8 '12 at 18:07

This question came from our site for theoretical computer scientists and researchers in related fields.

• No, they are the same for all values of $n$. If they could be different then the definition would be meaningless. – Yuval Filmus Sep 8 '12 at 5:10
• A close look at the definitions will reveal the truth. $\exists c.\ \forall n.\ \dots$ is not the same as $\forall n.\ \exists c.\ \dots$. – Raphael Sep 8 '12 at 21:40

No, the constants $c_1,c_2$ are the same for all values of $n$. If they could depend on $n$ then the definition would be meaningless since $\Theta(g(n))$ would contain all positive functions. Indeed, suppose $f,g$ are two positive functions. Then for all $n$, $$c_1g(n) \leq f(n) \leq c_2g(n) \text{ for } c_1 = c_2 = \frac{f(n)}{g(n)}.$$
... are the constants $c_1$ and $c_2$ different for every value of $n$?
A quantity $c$ is a constant only if its value is unaffected by changes to the asymptotic variable (i.e. $n$). Therefore, $c$ must have the same value for all values of $n$.
Read the notation aloud. "There exist constants $c_1, c_2$ that are greater than $0$ such that for all $n$ greater than some $n_0$, $c_1g(n)$ is less than or equal to $f(n)$ and $f(n)$ is less than or equal to $c_2g(n)$.
Hence, $c_1$ and $c_2$ are constants that apply for all $n > n_0$.