# In which O-class does my Θ-result belong?

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?

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.)

• (sound of screeching breaks) You called? – Raphael Jun 8 '16 at 11:20
• 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). – Raphael Jun 8 '16 at 11:22
• @Raphael Can't you at least find a technicality to arrest him on? – David Richerby Jun 8 '16 at 11:45
• Yes, suspect just confirmed there could be more than one correct answer – Mike Red Jun 8 '16 at 12:16
• @MikeRed OK, false alarm. Move along everybody. Nothing to see here. Nothing to see. Move along, please! – David Richerby Jun 8 '16 at 12:24