# A little confusion with Big Theta time complexity

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

• The inequality must hold not just for n', but for EVERY n ≥ n'. May 19, 2022 at 8:20

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

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.

• What exactly is correct? n^2 is not in Big-Theta(n^3). May 19, 2022 at 8:21
• Thank you. I have definitely traced the bug in my thinking. May 19, 2022 at 12:56