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;


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.

  • $\begingroup$ If you care only about asymptotic growth of T(n), does it really matter if it is (n+1)/3 or n/3 ? Why don't you set (n+1)/3 = m and see if it does? $\endgroup$ – Sorrop Nov 28 '16 at 22:23
  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – David Richerby Nov 28 '16 at 23:09

Your Answer

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

Browse other questions tagged or ask your own question.