title: Recurrence Relation/Time Complexity for finding average height of a BST
body: <p>Say we have an initially empty BST where I perform n arbitrary inserts, how would I find the average height of this BST?  The expression/pseudocode for this would be (if I'm not mistaken): </p>
  
  <pre><code>H(T) = 1 + max(H(T.left), H(T.right))
  </code></pre>
  
  <p>My guess at a recurrence relation for this would be <code>T(n) = 1 + 2*T(n/2)</code>, but I'm not sure if this is correct.</p>
  
  <p>Now here's my dilemma, if my recurrence relation is correct, how do I calculate the average complexity for my average height algorithm?</p>