I've just started with recurrence relations. I know that the divide and conquer relation in merge sort is given by,
$M(n) = 2M(n/2) + n$
Question: A divide and conquer relation is given $$a_n = 2a_{n/2}(n-1) \text{ for } n \geq 2 \text{ and } a_1 = 0$$ Show that it represents merge sort. Solve the above recurrence relation and find the complexity of merge sort.
I'm not able to figure out how to start with this problem. This question is from the previous year's exams at my college, and any clarification from them on print errors is not possible soon. I can come up with the solution but I am not sure about these steps:
- The question has $a_{n/2}$, a fraction in the subscript, I think that it is a print error, instead of $a(n/2)$ and $a(n)$ they have printed $a_{n/2}$ and $a_n$.
- If I am assuming the print error theory, the question becomes, $a(n) = 2a(n/2)(n-1)$, which is not making sense.
- If the question is asking me to solve a recurrence relation, then chances are that it should of the form $a_n = a_{n-1} + f(n)$ etc. which this one is not.
It'd be really helpful if you can help me figure out:
- Do you think this question is correct?
- How can I proceed to solve it? I know how to solve linear homogeneous and nonhomogeneous recurrence relations but this isn't applicable in any of the cases.
Any directions and help will be really great.