Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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) \}.$
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)}.$$
Actually the answer lies already in your question. You write:
... 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$.
