title: Better Understanding Big O and Big Theta with a divide and conquer search
body: <blockquote>
    <p>A divide and conquer algorithm takes an array of size n as input and
    makes two recursive calls on arrays of size n/2. Then, after an
    additional O(n) work, it produces an output. The running time should
    be:</p>
    
    <p>a) Θ(n)<br>
    b) Θ(n log n)<br>
    c) Θ(n^(log₂(3)))<br>
    d) Θ(n²)</p>
  </blockquote>
  
  <p>I'm trying to review for an exam and this is a question off the review. Intuitively I want to say b, because I know divide and conquer algorithms run at O(n log n), but the fact the answers are in Big Theta completely throws me off. Why would the question refer to "an additional O(n) work" then supply answers in Big Theta?</p>
  
  <p>Any help appreciated. I'm just trying to understand this better.</p>