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 ... :
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))
...
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)
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With