Big O Analysis with Recursion Tree of Stooge Sort

Question

I am trying to find the Big O for stooge sort. From Wikipedia

algorithm stoogesort(array L, i = 0, j = length(L)-1)
     if L[j] < L[i] then
         L[i] ↔ L[j]
     if j - i > 1 then
         t = (j - i + 1)/3
         stoogesort(L, i  , j-t)
         stoogesort(L, i+t, j  )
         stoogesort(L, i  , j-t)
     return L

I am bad at performance analysis ... I drew the recursion tree

I believe the ... :

• height: log(n)
• work on level 0: n // do I start from level 0 or 1?
• work on level 1: 2n
• work on level 2: 4n
• work on level 3: 8n
• work on level log(n): (2^log(n))n = O(n^2)? 2^log2(n) = n, but its what does 2^log3(n) actually give?

So its O(n^2 * log(n)) = O(n^2)? Its far from Wikipedia's O(n^(log3/log1.5)) ...

Answer 1

You can use the Master Theorem to find this answer. We can see from the Algorithm that the recurrence relation is:

T(n) = 3*T(2/3 n) + 1

Applying the theorem:

f(n) = 1 = O(n^c), where c=0. a = 3, b = 3/2 => log3/2(3) =~ 2.70

Since c < log3/2(3), we are at Case 1 of the Theorem, so:

T(n) = O(n^log3/2(3)) = O(n^2.70)

Answer 2

The size of the problem at level k is (2/3)^kn. The size at the lowest level is 1, so setting (2/3)^kn = 1, the depth is k = log_1.5 n (divide both sides by (2/3)^k, take logs base 1.5).

The number of invocations at level k is 3^k. At level k = log_1.5 n, this is 3^log_1.5n = ((1.5)^log_1.53)^{log_1.5 n} = ((1.5)^log_1.5n)^{log_1.5 3} = n^log_1.53 = n^{log 3/log 1.5}.

Since the work at each level increases geometrically, the work at the leaves dominates.