3
$\begingroup$

My understanding is that the answer is yes. To be θ(n) implies O(n), which itself implies O(n^2).

In other words, a function that is tightly bounded by n is trivially upper-bounded by n^2 as well.

The TA of my class tells me that I'm wrong, that a function that is tightly bounded by n cannot be upper-bounded by anything other than n. Which doesn't sound right to me, as O(n) is but a subset of O(n^2).

$\endgroup$
4
  • 5
    $\begingroup$ Your TA is wrong and you are correct. $\endgroup$
    – ryan
    Sep 27, 2019 at 3:46
  • 5
    $\begingroup$ I'm voting to close this question as off-topic because this is a check-my-answer question and the answer is clearly "yes". $\endgroup$
    – xskxzr
    Sep 27, 2019 at 3:59
  • 1
    $\begingroup$ The TA ought to read the definition of Big-O carefully, and then it is obvious that the answer is "Yes". $\endgroup$
    – gnasher729
    Sep 27, 2019 at 21:50
  • $\begingroup$ @xskxzr I'd say the question is "what is a good argument to demonstrate that I'm right when the other person is in authority and not very bright". OP is right and knows they are right, no need for checking, but for help how to explain it to the TA. $\endgroup$
    – gnasher729
    Sep 28, 2019 at 14:23

0