title: Asymptotic time complexity, Big oh and Theta analysis. Is this a trick question though
body: <p>Here's the question:</p>
  
  <p>Consider the following sorting algorithm: I. Insert the given input A[1], A[2], ..., A[n] into a binary search tree T in the given order, starting from an empty tree; II. Do an inorder traversal of T to output the elements in non-decreasing order. (a) What is the worst case time for the algorithm? (b) What is the best case time for the algorithm?</p>
  
  <p>My answer:</p>
  
  <p>I created a BST in <code>t(n) = 2(n/2) + n</code> as we have to go through each individual element, I also then printed out the BST inorder in <code>t(n) = 2(n/2) + n</code> as again we have to go through each element. I then added the time complexities together ending with, <code>t(n) = 4(n/2)+2n</code>.</p>
  
  <p>According to Master's method, this complies with case 1. Making it <code>θ(n^2)</code>. If it is <code>θ(n^2)</code>, this answers both a and b of the question. I don't see how there could be a better performance, or in that case a worse performance.</p>
  
  <p>Is this a trick question?</p>