1
$\begingroup$

In a multiple-choice test, I'm asked to solve the recurrence $T(n)=2T(n/2)+n/2$. I've done this using the master theorem: $f(n)=n/2$, $a=2$, $b=2$, so we're in the second case and $T(n)=\Theta(n\log n)$.

But the possible answers are $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$ and $O(n^2/\log n)$ and more than one may be correct. What do I do now?

$\endgroup$
2
$\begingroup$

You've solved the recurrence more precisely than the test-setter was expecting you to. You know that $T(n)=\Theta(n\log n)$, which means that $T(n) = O(n\log n)$ and $T(n) = \Omega(n\log n)$, and that gives you the answer.

(By the way, I didn't check that you solved the recurrence correctly, but you can do that yourself. Answer checking is off-topic here, and you didn't ask for it, so I focused on the rest of your question.)

$\endgroup$
  • 1
    $\begingroup$ (sound of screeching breaks) You called? $\endgroup$ – Raphael Jun 8 '16 at 11:20
  • 1
    $\begingroup$ I'd say there are three correct answers, and I'd definitely mark all of them. To be fair, we don't know that the author wrote "there is exactly one correct answer"; Mike may be expected to cross all correct answers, in which case the question makes perfect sense (as far as MC questions go). $\endgroup$ – Raphael Jun 8 '16 at 11:22
  • $\begingroup$ @Raphael Can't you at least find a technicality to arrest him on? $\endgroup$ – David Richerby Jun 8 '16 at 11:45
  • $\begingroup$ Yes, suspect just confirmed there could be more than one correct answer $\endgroup$ – Mike Red Jun 8 '16 at 12:16
  • 1
    $\begingroup$ @MikeRed OK, false alarm. Move along everybody. Nothing to see here. Nothing to see. Move along, please! $\endgroup$ – David Richerby Jun 8 '16 at 12:24

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.