title: Big O Analysis with Recursion Tree of Stooge Sort
body: <p>I am trying to find the Big O for stooge sort. From Wikipedia</p>
  
  <pre><code>algorithm stoogesort(array L, i = 0, j = length(L)-1)
       if L[j] &lt; L[i] then
           L[i] ↔ L[j]
       if j - i &gt; 1 then
           t = (j - i + 1)/3
           stoogesort(L, i  , j-t)
           stoogesort(L, i+t, j  )
           stoogesort(L, i  , j-t)
       return L
  </code></pre>
  
  <p>I am bad at performance analysis ... I drew the recursion tree</p>
  
  <p><img src="https://i.imgur.com/CJz9j.png" alt=""></p>
  
  <p>I believe the ... :</p>
  
  <ul>
  <li>height: <code>log(n)</code></li>
  <li>work on level 0: n    // do I start from level 0 or 1?</li>
  <li>work on level 1: 2n</li>
  <li>work on level 2: 4n</li>
  <li>work on level 3: 8n</li>
  <li>work on level log(n): <code>(2^log(n))n = O(n^2)</code>? <code>2^log2(n) = n</code>, but its what does <code>2^log3(n)</code> actually give? </li>
  </ul>
  
  <p>So its <code>O(n^2 * log(n)) = O(n^2)</code>? Its far from Wikipedia's <code>O(n^(log3/log1.5))</code> ...</p>