Will Big Theta not apply when $f(n)$ and $g(n)$ are of different order?

Question

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.

Answer 1

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.

Answer 2

$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)$]

Answer 3

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