1

State true or false x=Θ(n4), y=Θ(n2) therefore x/y=Θ(n2)

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 n4+...... and for y we have a polynomial like n2+... so if we divide x/y the ans should have the highest power of n2 and the resultant polynomial will be like n2+.... So it should be Θ(n2)

1 Answer 1

5

It's true. There are positive constants c1, c2, c3 and c4 such that, for all large enough n, c1n4xc2n4andc3n2yc4n2. Therefore, c1c4n2xyc2c3n2, i.e., x/y=Θ(n2).

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=n4+logn.

4
  • 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.
    – ryan
    Commented Aug 4, 2019 at 1:20
  • @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. Commented Aug 4, 2019 at 11:21
  • 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(n2)Θ(n2).
    – ryan
    Commented Aug 4, 2019 at 23:40
  • @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 Θ(n4) and y similarly defines some some function gΘ(n2). 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'." Commented Aug 5, 2019 at 9:12

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.