1
$\begingroup$

State true or false $x=\Theta(n^4)$, $y=\Theta(n^2)$ therefore $x/y=\Theta(n^2)$

I think the ans is true,but in the book it says false. What is the explanation?

My reason for thinking it to be true is that say for x we have a polynomial $n^4$+...... and for y we have a polynomial like $n^2$+... so if we divide x/y the ans should have the highest power of $n^2$ and the resultant polynomial will be like $n^2$+.... So it should be $\Theta(n^2)$

$\endgroup$
5
$\begingroup$

It's true. There are positive constants $c_1$, $c_2$, $c_3$ and $c_4$ such that, for all large enough $n$, $$c_1n^4 \leq x\leq c_2 n^4 \quad\text{and}\quad c_3n^2\leq y\leq c_4n^2\,.$$ Therefore, $$\frac{c_1}{c_4}n^2 \leq \frac{x}{y}\leq \frac{c_2}{c_3} n^2\,,$$ i.e., $x/y=\Theta(n^2)$.

By the way, in your argument, you say that $x$ and $y$ are polynomials. That's not necessarily true – for example, we could have $x=n^4+\log n$.

$\endgroup$
  • $\begingroup$ There is ambiguity in the fact that $x$ and $y$ are functions of $n$ but that isn't shown in the question or answer. It should be $x(n)/y(n)$ I believe. The input to the function should be specified to get a result. This could be why the book says it is false. $\endgroup$ – ryan Aug 4 at 1:20
  • $\begingroup$ @ryan If it's ambiguous, there must be some other meaning: what's the other meaning? I don't see any real problem with the notation used. If the point of the question is that the student is supposed to say "It's false" for the sole reason that the notation isn't precise enough, then it's a terrible question. $\endgroup$ – David Richerby Aug 4 at 11:21
  • $\begingroup$ The only problem I would potentially see is, without input, it's not 100% clear that $x$ and $y$ are functions on the same input $n$. For instance $x(n) / y(n^2) \not\in \Theta(n^2)$. $\endgroup$ – ryan Aug 4 at 23:40
  • $\begingroup$ @ryan If that was the intention, it is completely unreasonable. The only reasonable interpretation that I can see is that $x$ stands for some expression such that the function $f$ that maps $n$ to $x$ is $\Theta(n^4)$ and $y$ similarly defines some some function $g\in \Theta(n^2)$. We're being asked about the expression $x/y$, which corresponds to the function mapping $n$ to $f(n)/g(n)$. Anything else seems like answering the question "Do domestic cats eat elephants?" with "Well, that's kind of ambiguous. There might be a brand of cat food called 'elephants'." $\endgroup$ – David Richerby Aug 5 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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