Recurrence relation for strange sort

Question

I am comfortable with the recurrence relations for the Fibonacci series and for binary search, but I don't know how to find the recurrence relation for this algorithm:

Algorithm strange-sort(A[0,,,,,,n-1])
       if n=2 and A[0]>A[1]
       {
              swap(a[0],a[1])
       }
       else if n>2
       {
              m=ceiling(2n/3)
              strange-sort(A[0.....m-1])
              strange-sort(A[n-m......n-1])
              strange-sort(A[0......m-1]) 
       }

How would I get a recurrence relation for this algorithm? What does it solve to?

Answer 1

This is the Stooge Sort algorithm. Wikipedia says that the runtime is O(n^{log 3 / log 1.5}), and by coming up with the right recurrence we can see why.

Notice that each recursive call does O(1) work and then make three recursive calls of size 2n / 3. This gives us the recurrence relation

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

We can now use the Master Theorem to solve this. Here, a = 3, b = 3/2, and d = 0. Since log_b a = log_1.5 3 > 0, by the Master Theorem this solves to O(n^{log_1.5 3}). Using properties of logarithms, this rearranges to O(n^{log 3 / log 1.5}), which is about O(n^{2.70951129135...}).

Hope this helps!