1
$\begingroup$

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) \}.$

$\endgroup$
  • 12
    $\begingroup$ No, they are the same for all values of $n$. If they could be different then the definition would be meaningless. $\endgroup$ – Yuval Filmus Sep 8 '12 at 5:10
  • 5
    $\begingroup$ 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$. $\endgroup$ – Raphael Sep 8 '12 at 21:40
10
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy