Date: 06/17/06 (Algorithms)    Keywords: no keywords

I've been reading texts list the recurrence relation for mergesort as Mergesort_n =2 * Mergesort_n-1 + n.

However, one of the things that these texts don't make clear is if this recurrence relation is true for all mergesorts...it seems to me that mergesort that copies arrays as opposed to in-place sorting would have a difference recurrence relation; specifically, it seems to me like it would be Mergesort_n =2 * Mergesort_n-1 +2 n. While this still resolves to Theta(n log n) efficiency, I'm surrprised that texts don't differentiate between in-place and copying. But I'm pretty new to recurrence analysis, so am eager to read any intelligent discussion on the matter...

Source: http://community.livejournal.com/algorithms/78564.html