title: The proof for the complexity of sorting algorithms
body: <p>The theorem denotes that:</p>
  
  <p>Any comparison sorting algorithm performs &Omega;(nlg(n)) comparisons in the worst case.</p>
  
  <p>To prove that I found:</p>
  
  <p>Looking the worst case number of comparisons that an algorithm performs, means the longest path from the root to a leaf in its decision-tree.</p>
  
  <p>As a binary tree of height h has at most 2^h leafs, and there are n! permutations (output), we have:</p>
  
  <blockquote>
    <p>2^h ≥ n!</p>
  </blockquote>
  
  <p>I understand that we can rewrite <code>2^h ≥ n!</code> as <code>h ≥ log2(n!)</code> but how can we end up with:</p>
  
  <blockquote>
    <p>h ≥ log2(n!) = &Omega;(n*lg(n)) ?</p>
  </blockquote>