Find the recurrence relation for the following algorithm

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!

• It looks correct for me :) Feb 25, 2021 at 17:18
• Do you have a specific question? We discourage "please check whether my answer is correct" questions, as they're unlikely to be of any use to others in the future, and we're looking to build up an archive of high-quality questions and answers that will be useful to others in the future.
– D.W.
Feb 26, 2021 at 0:18

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$$.

• Brillant explanation! Thanks for your support. Feb 26, 2021 at 18:08
• Just to be sure, if there are two or more comparisons in 'if' statement, it will always be $O(1)$, right? Should I consider as only one time step? Feb 26, 2021 at 18:11
• Every atomic instruction takes one step, that’s the usual assumption. Feb 26, 2021 at 22:10