Finding recurrence relations of an algorithm

Question

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?

Answer 1

Well, this statement is (presumably) the conclusion of a discussion, or at least a statement, of the algorithm in question. Without the details I can only made educated guesses, which would go like this:

• the first thing the algorithm does is check if it's being asked to process 0 or 1 elements. If that's true, it returns immediately. Thus, then n < 2, there is a fixed cost - call it b
• For n >= 2, the algorithm splits its input into two pieces, each of size n/2, and invokes itself on each piece. Each such invocation will have a cost of t(n/2), and there are two such invocations
• There is then an additional cost to merge the two pieces back together - this cost will be proportional to n - call it b times n

The only slight oddity is that it's not entirely obvious why the two constant factors that arise should be the same - but part of the point of big-O analysis is that constant factors eventually don't matter.

Answer 2

The merge sort algorithm can be summarized as:

mergesort (array A) {
   mergesort (first half of A);
   mergesort (second half of A);
   merge the two halves and return;
}

There is an O(N) algorithm to merging two arrays of length N, i.e. its complexity is bN for some constant b > 0.

Assuming the complexity of mergesort is T(N). Since half of N is N/2, we see that:

mergesort (array A) {                    T(N)    =
   mergesort (first half of A);          T(N/2)  +
   mergesort (second half of A);         T(N/2)  +
   merge the two halves and return;       bN
}

which explains the N ≥ 2 case.

The N < 2 case (the base case where you stop the recursion) is trivial.

Answer 3

T(n) = c if n < d
     = A*T(n/b) + f(n)

where d>=1 and there are A subproblems and the subproblems are at most n/b size. f(n) is the total additional time needed to divide the problem into subproblems and merge the subproblem solutions into a solution to the entire problem.

this is for divide and conquer algorithms.

I wonder why there are 2 subproblems in merge sort?