Finding recurrence relations of an algorithm
- by Roarke
I'm reading my algorithms text book, and I'm reading about recurrence relations and finding the algorithms big O complexity. I run across this line
"In the case of the merge-sort algorithm, we get the recurrence equation:
t(n) = b if n < 2
= 2t(n/2) +bn if n >= 2
for b > 0
my response was "how the heck did we know that?!?!"
So i'm wondering if there is a systematic approach, or just a logical way of getting these recurrence relations from the algorithms
can some one explain where the b and the two 2's come from?
