title: Worst case running time of constructing a BST?
body: <p>Could someone explain to me how the Worst case running time of constructing a BST is n^2? I asked my professor and the only feedback i received is </p>
  
  <p>"Because the tree is linear to the size of the input. The cost is 1+2+3+4+...+(n-1)."</p>
  
  <p>Can someone explain this in a different way? Her explanation makes me think its O(n)....</p>