Yet another sorting algorithm

Computer Science Level 5

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.

The answer is 2.71.

1 solution

A Former Brilliant Member
Jul 25, 2016

Note that the time complexity $T(n)$ follows the following recurrence:

$T(n) = 3T \left( \frac{2n}{3} \right) + \Theta(1)$

We now use the master theorem to conclude that $T(n) \in \Theta\left (n^{\log_{\frac{3}{2}}3 } \right)\\\implies \alpha = \log_{\frac{3}{2}}3 \approx 2.71$

Yet another sorting algorithm

The answer is 2.71.

1 solution

0 pending reports