2
$\begingroup$

Given the below algorithm enter image description here

How would one go about setting up a recurrence for both that merging algorithm AND using this "new" merging algorithm in a traditional merge sort?


What I've tried

For the merge algorithm, I've concluded that the recurrence is $T(n) = 2T(n/2) + (n-1)$ or $T(n) = 2T(n/2) + n$. I suspect this is my first error.

When combining it with the traditional merge sort, $T(n) = 2T(n/2) + n$, we'd want to remove the $+n$ because we're going to replace it with our own merge. This new recurrence is $T(n) = 2T(n/2) + 2T(n/2) + n = 4T(n/2) + n$. According to the Master's theorem, this yields a running time of $O(n^{log_2 4})$ which is $O(n^2)$. I know this isn't correct, because I already happen to know that the running time of an odd-even merge sort is $O(n log n)$.

$\endgroup$
5
  • 1
    $\begingroup$ You're trying to derive two different functions there -- one for the time it takes to merge two list of $n$ elements each, and one for the time it takes to sort $n$ elements. When you notate both of them with the same letter $T$, you're creating hopeless confusion that invalidates most of what you're doing. $\endgroup$
    – hmakholm left over Monica
    Commented Aug 28, 2015 at 2:25
  • $\begingroup$ Don't I need the recurrence of the merge in order to get the recurrence of the new merge sort? $\endgroup$
    – throwawayhmwk
    Commented Aug 28, 2015 at 2:39
  • $\begingroup$ x @throw: Yes, but they are still two different functions. You can't name them both $T$ and expect things to make sense. $\endgroup$
    – hmakholm left over Monica
    Commented Aug 28, 2015 at 3:32
  • $\begingroup$ @HenningMakholm What would be the right way to do this then? I have no clue how to combine them if they're different. I've been told that once I figure out the recurrence for the merge algorithm, the merge sort algorithm will come naturally. $\endgroup$
    – throwawayhmwk
    Commented Aug 28, 2015 at 3:50
  • $\begingroup$ x @throw: The right way to do it would be to use two different names for the two different functions. (It is unclear to me how this is a difficult concept). Then solve the recurrences one by one -- since the merge operation is used as part of the sorting algorithm you need to solve its recurrence before you can plug the solution into the other recurrence and start solving that. $\endgroup$
    – hmakholm left over Monica
    Commented Aug 28, 2015 at 4:27

0

Reset to default

You must log in to answer this question.