# Complexity of Merge Sort that splits in a random position

I got a question that I don't fully understand: Given a new algorithm to merge sort (AKA mergesort2) that instead of splitting the list in the middle it splits the list in a random number between $$1$$ and $$n-1$$. Also, we know the probability of getting $$1$$ is $$2/n$$ and to every other number $$1/n$$.

I have tried again and again and came up with the regular when doing the "average case" $$\Theta \ (n \log n)$$ and of the merge sort algorithm and "worst case" $$O (n^2)$$ but I'm not sure about it.

Pseudo-Code:

   MergeSort2(A,p,q)
if(p=q) then return
i = random number from (1...q-p)
MergeSort2(A, p,   p+i-1)
MergeSort2(A, p+i, q)
Merge(A, p, p+i-1, q)


How I did the calculations of the $$O (n^2)$$ "worst case" when I split it to $$1$$ and to $$n-1$$ every time: (if it's correct)

$$T(n)= T(1)+T(n-1)+O(n)$$

When $$T(1)$$ is the single number, $$T(n-1)$$ is the rest list and $$O(n)$$ is the merge

\begin{align*} T(n) &= (T(1)+T(n-2)+O(n)) + T(1)+O(n) & \text{second recursive call}\\ &= (T(n-3)+T(1)+O(n)) +2T(1)+2O(n) & \text{third recursive call}\\ & \vdots\\ T(n) &= T(n-k)+kT(1)+kO(n) & k^{th}\text{ recursive call} \end{align*}

Now we know that $$T(1) = O(1)$$ as it doesn't do anything.

In order to get to our stop condition, we need the $$T(n-k)$$ will be $$T(1)$$.

So to do so we will take $$k = n-1$$.

Therefore we will get the following:

$$T(n) = T(1)+(n-1)O(1)+(n-1)O(n) \implies T(n) = O(n^2)$$

How do I calculate properly the complexity of the given algorithm?

• Since the complexity now depends on a random value, there are multiple reasonable approaches. You can look at the worst case, as usual. However, that specific case happens with a low probability. A common alternative is to look at the expected running time. What type of complexity are you interested in? – Discrete lizard Apr 24 '19 at 10:29
• @Discretelizard in the question we did not get any "expected" run time to follow we are supposed to figure out what is the O() of the algorithm. That what made the confusion - how do I calculate it with all the probabilities. – EladAskenazi Apr 24 '19 at 10:34
• If it is unclear what sort of run time you need to compute, you should ask that to the one that gave you the assignment. I suppose you need to compute the worst case running time, but then the probabilities are not needed. – Discrete lizard Apr 24 '19 at 11:20
• @Discretelizard I have come up with the calculation to the "worst case" do take a look and advice me if it's correct – EladAskenazi Apr 24 '19 at 11:25

If you always split on index $$n/100$$ the complexity is going to be $$O(n \log n)$$. So in reality most split positions will give you a reasonable complexity.

This means that on average you will get a good split position (half of the splits will be between $$n/4$$ and $$3n/4$$, 90% of the splits will be between $$n/20$$ and $$19n/20$$). This is why using an random element in quicksort also give good performance except for that one in a billion chance the time it pathologically selects the worst pivot.

• I'm not sure I fully understand how you concluded it. We know that the worst case is every time we split the list in to 1 and n-1 elements. And we know that the probability to get 1 is double then any other number. Argo I'm not sure how do I conclude that it will still be nlogn.. – EladAskenazi Apr 24 '19 at 12:19

For definiteness, let us suppose that the $$T(1) = 1$$ and that if the split is $$k+(n-k)$$ then the running time is $$T(k) + T(n-k) + n$$. The recursion for the worst-case running time is therefore $$T(n) = \begin{cases} \max_{1 \leq k \leq n-1} T(k) + T(n-k) + n & \text{if } n > 1 \\ 1 & \text{if } n = 1. \end{cases}$$

In order to calculate the worst-case complexity, we need both an upper bound and a lower bound. You already gave the lower bound: $$T(n) \geq T(1) + T(n-1) + n = T(n-1) + n+1.$$ Iterating this easily yields $$T(n) = \Omega(n^2)$$.

In the other direction, let us prove that $$T(n) \leq n^2$$ for all $$n$$. The base case is clear. For the inductive case, $$T(k) + T(n-k) + n \leq k^2 + (n-k)^2 + n \leq 1 + (n-1)^2 + n = n^2 - n + 2 \leq n^2,$$ since $$n \geq 2$$. It follows that $$T(n) = \Theta(n^2)$$.

(In fact, with some more work you should be able to show that $$k=1$$ is indeed (together with $$k=n-1$$) the worst choice.)

Let us now proceed to the average case running time (i.e., the expected running time), which satisfies the recurrence $$S(n) = \begin{cases} \frac{1}{n-1}\sum_{1 \leq k \leq n-1} [S(k) + S(n-k)] + n & \text{if } n > 1 \\ 1 & \text{if } n = 1. \end{cases}$$ We can simplify the inductive case to $$S(n) = \frac{2}{n-1} \sum_{1 \leq k \leq n-1} S(k) + n.$$ This implies that for $$n \geq 2$$, $$n S(n+1) = 2(S(1) + \cdots + S(n)) + (n+1)n, \\ (n-1) S(n) = 2(S(1) + \cdots + S(n-1)) + n(n-1).$$ Subtracting gives $$nS(n+1) - (n-1)S(n) = 2S(n) + 2n \Longrightarrow nS(n+1) = (n+1)S(n) + 2n \Longrightarrow \\ \frac{S(n+1)}{n+1} = \frac{S(n)}{n} + \frac{2}{n+1}.$$ This shows that $$\frac{S(n)}{n} = \frac{2}{n} + \frac{2}{n-1} + \cdots + \frac{2}{2} + \frac{S(1)}{1} = 2H_n - 1 = \Theta(\log n),$$ and so $$S(n) = \Theta(n\log n)$$.

• very high ranked answer. like ! is it true that we say this question is exactly has recurrence of randomized quick sort average and worst case time? – Mouna Mokhiab Feb 2 at 14:51
• Yes, it should be essentially the same. – Yuval Filmus Feb 2 at 14:53