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

3 Answers 3

11
$\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 and acknowledge that you have read and understand our privacy policy and code of conduct.