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

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.

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

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.

• Ah I see, that actually helps with the formal negation! It kind of makes more sense as well when you mentioned arbitrary variables. Thanks! Feb 6, 2022 at 10:02
• 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. Feb 6, 2022 at 10:15

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

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