1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Discrete lizard Apr 24 at 10:29
  • $\begingroup$ @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. $\endgroup$ – EladAskenazi Apr 24 at 10:34
  • $\begingroup$ 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. $\endgroup$ – Discrete lizard Apr 24 at 11:20
  • $\begingroup$ @Discretelizard I have come up with the calculation to the "worst case" do take a look and advice me if it's correct $\endgroup$ – EladAskenazi Apr 24 at 11:25
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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.. $\endgroup$ – EladAskenazi Apr 24 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.