title: Difference between the time complexity required to build Binary search tree and AVL tree?
body: <p>While I was learning Binary search tree(Balanced and unbalanced), I come up with questions which I need to resolve:</p>
  
  <ol>
  <li><p>If I construct a Binary search tree(Not necessary to be balanced) , using n elements then what is the total time complexity for tree construction ?</p></li>
  <li><p>If an AVL tree is constructed from n elements then what is the time complexity to contruct that AVL tree ? </p></li>
  </ol>
  
  <p>Should it be more than nlog(n) ?  because we need lots of rotation for AVL tree construction . </p>
  
  <p>I know that insertion and deletion operation in AVL tree will be of log(n) order(same is true if binary search tree constructed with random elements has log(n) height). </p>
  
  <p>But I need to know about overall  tree construction cost and how it varies as I need to use balanced search tree for sorting purpose . </p>