A little confusion with Big Theta time complexity

Question

I came across one Big Theta expression:

Here I am thinking this expression to be valid. But please correct me as the answer doesn't goes in the same way. As per definition of Big Theta.. any function f(n) execution time must lie between c1g(n) (f(n) is greater than this function) and c2g(n)(f(n) is smaller than this function) for some input size n greater than n'. And if I take the input size (n') as 1 than n^2 is 1 & n^3 is 1. c1 and c2 can be real constants. taking c1 as 1/2 and c2 as 2 then as per Big theta it should 2 >1>1/2.. and as per me this holds true while in reality the above statement stands to be false

Answer 1

"for some input size $n$ greater than $n'$" is wrong. The correct statement is "for all input sizes $n$ greater than $n'$".

Obviously,

$$\frac{n^3}2\le n^2\le 2n^3,$$

which is equivalent to

$$\frac12\le n\le 2,$$ cannot hold for unbounded $n$.

---

More generally,

$$\frac1{c_2}\le n\le\frac1{c_1}$$ is incompatible with $$n>n'.$$

---

If you think of it a little, the condition "for some $n$" would be a nonsense, because if you take any $f,g,n'$ and some $n>n'$, then

$$c_1:=\frac{f(n)}{2\,g(n)},c_2:=\frac{2\,f(n)}{g(n)}$$ always makes

$$c_1\,g(n)\le f(n)\le c_2\,g(n)$$ and $\color{red}{f(n)\in\Theta(g(n))}$.

Answer 2

If $f(n) \in O(g(n))$ and $g(n) \in O(f(n))$ then $f(n) \in \Theta(g(n))$, otherwise $f(n) \not\in \Theta(g(n))$.

$n^2 \in O(n^3)$ but $n^3 \not\in O(n^2)$ so $n^2 \not\in \Theta(n^3)$.

It works analogously to regular numbers. If $x \leq y$ and $y \leq x$ then $x=y$, otherwise $x \neq y$.

The error in your thinking is that $f(n) \in \Theta(g(n))$ is true only if $c_1g(n) < f(n) < c_2g(n)$ for all $n$ greater than some $n'$, not just a single example.