master theorem for divide and conquer

Mergesort is an example of divide-and-conquer strategy. Divide a problem into subproblems until getting to the smallest one (when there is one element in the array for mergesort) and then combine solutions of subproblems together.

The time complexity for divide-and-conquer problems is a little complicated and so is the proof of it. For example, in mergesort, T(n) = 1 if n = 1, and T(n) = T(ceiling of n/2) + T(floor of n/2) + dn if n > 1. Though the expression is long, it's based on the algorithm of mergesort and I find it easy to remember if understanding the algorithm.

To prove the time complexity of mergesort which is upper bounded by n*lgn, it is more difficult than proofs before in the course. Here, I need three steps. First, I need to find out the expression for T(n) when n = 2^k (k is a natural number) and using induction to prove it. Then I need to show that T(n) is monotonic (non-decreasing actually) also using induction. At last, I use the previous result to prove that T(n) < Xn*lgn. But at this point, another difficulty comes out. I have to figure out what X is. So I can make T(n) bigger to the expression in the form n *lgn times another coefficient, which is the X I want. After all that, I can say T(n) is upper bounded by n *lgn.

For time complexity of other divide-and-conquer problems, the steps are similar. The difference is that they are not necessarily divided into two parts, instead, to pieces of size n/b parts. There's really a lot of work, but generally, I need to remember three things:
1. Find out the expression for T(n) when n = b^k (k is a natural number)
2. Prove T(n) is monotonic.
3. Prove the time complexity using previous results.