While setting left=0, right=n-1 and A an array of n numbers, find out the running time complexity in terms of $\Theta$. Firstly find out the recurrence and then evaluate it by using the substitution technique. (MergeSort is a regular mergesort between the given 2 indexes, and Merge is of linear time complexity as the number of numbers in fields left and left+p, left+p and left+2p, left+2p and right.)
The code:
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+2p-1);
MergeSort(A,left+2p,right);
Merge3(A,left,left+p,left+2p,right);
}
}
This is what I did:
- Firstly let's notice the internal work of Sort is MergeSort and Merge3. because mergeSort gets $n-1-2\frac{n-1+2}{3}$ numbers to sort, the complexity of it would be $\Theta(n\log n)$. Because Merge3 is linear to the amount of numbers in its fields, then the time complexity would be the amount of numbers in array A. Thus, it's $\Theta(n)$. So finally, the "extra work" is of time complexity $\Theta(n+n\log n)=\Theta(n\log n)$
- Let's notice there are two recursive calls to Sort. First one is for function Sort with left+p-1-left range of numbers. so the size of the range is $\frac{n-2}{3}+1$. Thus it's a recursive call of type $T(\frac{n+1}{3})$. Same for second call of Sort
- So finally in TOTAL we get the recurrence $T(n)=2T(\frac{n+1}{3})+\Theta(n\log n)$
My Question is if it's correct? because it seems to be too complicated to evaluate the time complexity of this recursive function. I wouldn't ask if I got for example $T(n)=2T(\frac{n}{3})+\Theta(n\log n)$ instead. because the $n+1$ in the numerator makes it really hard to evaluate.
