0
$\begingroup$
void Sort(int A[], int left, int right)
{
    int p;

    if (left < right)
    {
        p = (right + left + 2)/3;

        Sort(A, left, left+p-1);
        Sort(A, left+p, left+2*p-1);

        MergeSort(A, left+2*p, right);

        Merge3(A, left, left+p, left+2*p, right);
    }
}

I need to convert this function into a mathematical expression in order to solve it's run-time complexity.

I know that MergeSort()'s complexity is of $\Theta(n \log n)$ and that Merge3()'s complexity is of $\Theta(n)$.

I can't figure how to transform this into a recursive mathematical expression.

$\endgroup$

closed as unclear what you're asking by D.W., frafl, Guy Coder, Luke Mathieson, András Salamon Nov 15 '13 at 15:38

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Tried anything? $\endgroup$ – G. Bach Nov 12 '13 at 12:59
  • 1
    $\begingroup$ This may help you stackoverflow.com/questions/2709106/… $\endgroup$ – Anton Nov 12 '13 at 13:00
  • 1
    $\begingroup$ What did you write down, where did it go wrong? $\endgroup$ – G. Bach Nov 12 '13 at 13:05
  • 1
    $\begingroup$ Do you understand that for the purpose of $\Theta$-analysis, most individual lines can be compacted to cost $1$? $\endgroup$ – Raphael Nov 12 '13 at 16:49
  • 1
    $\begingroup$ @Quaker I suggest you translate the algorithm line by line and show us your result. Then we can figure out where your problem lies. $\endgroup$ – Raphael Nov 12 '13 at 16:52
1
$\begingroup$

The key is to use right - left as $n$ for the parameter of the runtime recursion. What is the size of the subparts?

Closer hint:

Note that the algorithm separates the input part of the array in three approximately equal-sized parts; the first two are sorted recursively, the third with Mergesort. This should be reflected in your recurrence.

Almost finished:

Assuming Merge3 runs in time $\Theta(n)$ und MergeSort in time $\Theta(n \log n)$, you get a recurrence of the form

$\qquad\displaystyle T(n) \approx 2T(n/3) + \Theta(n) + \Theta(n/3 \log(n/3))$

since all parts have size $\approx p \approx n/3$. Solve this with the Master theorem and flesh out the details.

$\endgroup$
  • $\begingroup$ Master Theorem actually solves this like a magic but I need to solve it by using the recurrence on itself until I find a pattern which is insanely confusing. $\endgroup$ – Eran Nov 13 '13 at 10:42
0
$\begingroup$

Hint: Usual merge sort takes a list of size $n$, divides it into two halves, sorts the two halves recursively, then merges them in $O(n)$. Your routine take a list of size $n$, divides it into three thirds, sorts the first two recursively and the last one using mergesort (this detail is a bit strange; you'd expect all three parts to be sorted recursively), then merges them in $O(n)$.

$\endgroup$

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