1
$\begingroup$

I'm currently taking my algorithms class, and I learnt that Big theta is defined as follows:

$f(n) = \Theta(g(n))$ if there exist constants $c_1, c_2, n_0 > 0$ such that $0 ≤ c_1g(n) ≤ f(n) ≤ c_2g(n)$ for all $n ≥ n_0$.

So if our $f(n)$ and $g(n)$ are of the same order, say $n$ and $2n$, we can easily find a constant $c$ and an $n_0$, such that $n$ lies between $c_1(2n)$ and $c_2(2n)$ for all $n ≥ n_0$.

Suppose in contrast that our $f(n)$ and $g(n)$ are of different order, say $f(n)$ is $O(g(n))$ where $f(n) = n$ and $g(n) = n^2$. So technically, there will exist constants $c_1$ and $c_2$ such that $c_1(n^2)$ is less than $n$, and $c_2(n^2)$ is more than $n$. However, because $n^2$ is of a higher order than $n$, as $n$ increases, $n^2$ will surpass n eventually regardless of its constant, and thus the definition of $\Theta(n)$ where for all $n \ge n_0$ will never hold if our $g(n)$ and $f(n)$ eventually intersect each other (which will happen if they have different orders?).

Is this always the case? Or am I being too narrow-minded in thinking like this.

$\endgroup$
1
  • 1
    $\begingroup$ "Is this always the case?": what is your question exactly ? What do you mean by this ? $\endgroup$
    – user16034
    Mar 1, 2022 at 8:28

3 Answers 3

1
$\begingroup$

Because it's very important to use correct conditions for variables, let me firstly (for non-negative case) formally write definition for $\Theta$:

$$\Theta(g)=\Big\{f\colon \exists C_1>0,\exists C_2>0, \exists N\in\mathbb{N}, \forall n \gt N, C_1 g(n)\leqslant f(n) \leqslant C_2 g(n)\Big\}$$

Now to obtain $f\notin \Theta(g)$ we need formal negation of definition i.e. $$\forall C_1>0,\forall C_2>0, \forall N\in\mathbb{N}, \exists n \gt N,f(n)\lt C_1 g(n) \lor f(n) \gt C_2 g(n)$$

As you see in negation we shouldn't find constants $C_1, C_2$, but we work with them as with arbitrary variables. Now we are searching for $n$.

In example with $n^2 \notin \Theta(n)$ we can use, that for $\forall C\gt 0, \exists n\in\mathbb{N}$ for which we can write $n^2 \gt Cn$ i.e. $n \gt C$. As such, for example, we can take $n=\lfloor C \rfloor+1$. And, as last detail, if we want to fulfill also condition for $N$, then we can choose, for example, $n=\max(\lfloor C \rfloor+1, N+1)$. As answer to your question in title, we can see, that there is no problem with using Theta notation for different orders: additionally to written we have also $n \notin \Theta(n^2)$.

As to your intuitive considerations, then, at one glance, they seems correct, but it is difficult to mathematically agree or contradict them precisely, since these are not formal statements. Therefore, I prefer such proofs as I have given above.

$\endgroup$
2
  • $\begingroup$ Ah I see, that actually helps with the formal negation! It kind of makes more sense as well when you mentioned arbitrary variables. Thanks! $\endgroup$
    – kohrhea
    Feb 6, 2022 at 10:02
  • $\begingroup$ Yes. Difference from "finding $C$" to "for all $C$" is crucial - I am glad, that You find it helpful. Feel free to ask/discuss more when need. $\endgroup$
    – zkutch
    Feb 6, 2022 at 10:15
1
$\begingroup$

$f(n)=O(g(n))$ alone does not imply $f(n)=\Theta(g(n))$. [$3n-2\ne\Theta(n^2)$]

$f(n)=\Omega(g(n))$ alone does not imply $f(n)=\Theta(g(n))$. [$3n-2\ne\Theta(\sqrt n)$]

$f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$ together imply $f(n)=\Theta(g(n))$. [$3n-2=\Theta(n)$]

$\endgroup$
0
$\begingroup$

Big Theta is one possible formalization of the concept of two functions being of the same order.

There will exist constants $c_1$ and $c_2$ such that $c_1(n^2)$ is less than $n$, and $c_2(n^2)$ is more than $n$.

In fact, such a constant $c_1 > 0$ does not exist: if $n \ge 1/c_1$ then $c_1 n^2 \ge n$.

This shows that $n^2$ is not $O(n)$, and in particular, $n^2$ and $n$ don't have the same order.

In contrast, the other inequality does exist, showing that $n^2 = \Omega(n)$.

You can even show a stronger inequality: $n^2 = \omega(n)$ (look it up). This is the same as $$ \lim_{n\to\infty} \frac{n^2}{n} = \infty. $$ Hence we can say that $n^2$ has a large order than $n$.

You can show that $f(n)$ has a larger order than $g(n)$, in the sense that $f(n) = \omega(g(n))$, then the two functions don't have the same order, that is, it is not the case that $f(n) = \Theta(g(n))$.

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

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