Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Big O Analysis with Recursion Tree of Stooge Sort

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)) ...

like image 694
Jiew Meng Avatar asked Nov 15 '11 02:11

Jiew Meng


2 Answers

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(nc), 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(nlog3/2(3)) = O(n2.70)

like image 44
André Santos Avatar answered Sep 23 '22 09:09

André Santos


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 = log1.5 n (divide both sides by (2/3)k, take logs base 1.5).

The number of invocations at level k is 3k. At level k = log1.5 n, this is 3log1.5n = ((1.5)log1.53)log1.5 n = ((1.5)log1.5n)log1.5 3 = nlog1.53 = nlog 3/log 1.5.

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

like image 175
Per Avatar answered Sep 22 '22 09:09

Per