0
$\begingroup$

I came across one Big Theta expression: enter image description here

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

$\endgroup$
1
  • 1
    $\begingroup$ The inequality must hold not just for n', but for EVERY n ≥ n'. $\endgroup$
    – gnasher729
    May 19, 2022 at 8:20

2 Answers 2

0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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