Find the recurrence relation for the following algorithm

Question

The question requests to find the recurrence relation of the following algorithm and solve it using the characteristic equation.

\begin{align} &\text{SORT}(A[0\dots n-1])\colon\\ &\quad \text{if } n = 2 \text{ and } A[0] > A[1] \text{ then} \\ &\quad\quad \text{swap}(A[0],A[1]) \\ &\quad \text{else if } n > 2 \text{ then} \\ &\quad\quad m=\lceil 2n/3 \rceil \\ &\quad\quad \text{SORT}(A[0\dots m-1]) \\ &\quad\quad \text{SORT}(A[n-m\dots n-1]) \\ &\quad\quad \text{SORT}(A[0\dots m-1]) \end{align}

The recurrence equation that I found is $T(n) = 2 \cdot T(2n/3) + T(n/3) + 1$ with base case $T(2) = 5$.

The base case is $T(2) = 5$ because of 2 comparisons in the if statement plus 3 statements in swap() function.

I'm not sure whether what I've tried is correct or not. All help is appreciated!

Answer 1

Your recurrence relation is almost correct. Here are some small issues with it:

• The length of the array $A[n-m\ldots n-1]$ is $m$, not $n-m$.
• Your recurrence only holds when $n$ is divisible by 3. The exact length of the arrays in the recursive calls is $m = \lceil 2n/3 \rceil$.
• You are not handling arrays of length $1$.
• You are trying to count operations, but without a precise model of computation, this is really impossible. There are two common options here: either you count specific operations, for example only comparisons and swaps, or you just give up and replace everything with $O(1)$. Both options are common.

Accordingly, here are some more accurate solutions are:

• When counting only comparisons of array elements, the recurrence is $T(1) = 0$, $T(2) = 1$, and $T(n) = 3T(\lceil 2n/3 \rceil)$ for $n \geq 3$.
• When counting only swaps, the recurrence is the same as in the first bullet. Note that $T$ is actually an upper bound on the worst-case cost of your procedure.
• When counting both comparisons of array elements, the recurrence is the same as in the first bullet, with "$1$" replaced by "$2$".
• When counting the running time on a RAM machine (the standard computation model for analyzing algorithms), the recurrence is $$T(n) = \begin{cases} O(1) & \text{if } n \leq 2, \\ 3T(\lfloor 2n/3 \rfloor) + O(1) & \text{otherwise.} \end{cases}$$

One fine point is that except when counting comparisons, the recurrence $T$ is for an upper bound on the cost. The exact cost depends on the instance, and often we are interested in estimating the worst-case cost as a function of the input length (in this case, $n$). However, the recurrence for $T$ isn't even guaranteed to compute the worst-case cost: it could be too pessimistic. For example, it could be that no input causes all possible swaps to be performed. Nevertheless, $T(n)$ does upper-bound the cost of the procedure on any input of length $n$.