1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20  def floor(n):
"""Compute the floor function of n"""
return int(n)
def stoogy(A, i, j):
"""Sort A[i...j]"""
if A[i] > A[j]:
A[i] , A[j] = A[j] , A[i] #Swap A[i] and A[j]
if i + 1 >= j:
return
m = floor( (j  i + 1) / 3)
stoogy(A, i, j  m)
stoogy(A, i+m, j)
stoogy(A, i, j  m)
def sort(A):
"""Sort the list A[0..n]"""
stoogy(A, 0, len(A)  1)

The tight asymptotic bound of (\(\Theta\)  notation) of the sorting algorithm above(sort(A)
) can be expressed as \(\Theta(n^{\alpha})\)( \(\alpha \in \mathbb{R} \) ). Find \(\alpha\).
Details and Assumptions
 \(n\) is the size of the array to be sorted.