3

I'd like to know how I can solve a recurrence relation like the one from merge sort. I know how to solve recurrence equations that start with $a(n)=a(n-1)+(n-1)$, but I don't know how to solve recurrence equations that start with $a(2n)$ like for example the equation of merge sort. How do I solve $a(2n+1)=a(n)+a(n+1)+2n$?

Pp..
  • 5,973
Pieter Verschaffelt
  • 481
  • you can consider:Binary number – math110 Jan 25 '15 at 15:06
  • 1
    Can you quote the recurrence that you need? The last recurrence allows you to define $a(2n+1)$ once you have $a(n),a(n+1)$. This means that it doesn't allow you to define the value at some even values of the index. If the last recurrence is really the one you want and you want to solve it depending on an arbitrary given sequence of values for $a(2n)$ then you can transform it into a system of recurrences $b(n):=a(2n+1)$ and $c(n):=a(2n)$. – Pp.. Jan 25 '15 at 15:14
  • What do you mean by "solve" exactly? Find out whether $a(n) = \Theta(n \log n)$? Or some exact formula etc? – Aryabhata Jan 25 '15 at 15:19
  • By "solve" I mean that I have to change it to an equation in the form of a(k)=(k-1)*2^k + 1 (The solution to this recurrence relation). I just don't know how to come to this solution. Thank you already :) – Pieter Verschaffelt Jan 25 '15 at 16:22

0 Answers0