Recurrence Formula

T (n)    <    c₁                 for n < 1
                  2 T(n/2)+c₂n   for n > 1

Expand for Closed Form Equation

Expand up (without loss of generality, let n = 2^k):

T(1) < c₁
T(2) < 2T(1) + 2c₂ = 2c₁ + 2c₂
T(4) < 2T(2) + 4c₂ = 2(2c₁ + 2c₂) + 4c₂ = 4c₁ + 8c₂
T(8) < 2T(4) + 8c₂ = 2(4c₁ + 8c₂) + 8c₂ = 8c₁ + 24₂
T(16) < 2T(8) + 16c₂ = 2T(4) + 16c₂ = 2(8c₁ + 24₂) + 16c₂ = 16c₁ + 64₂

Do we see a pattern? This is important. Either try to determine the pattern or try to bring to bear all the information about the problem that you know. Remember that we know something about mergesort and expect nlogn

n=2     2c₁ + 2c₂     2 * 1
n=4    4c₁ + 8c₂     4 * 2
n=8    8c₁ + 24c₂     8 * 3
n=16   16c₁ + 64c₂     16 * 4
AH HA!

T(n) < nc₁ + n*logn c₂

OR another technique:

T(n) = 2 T(n/2)+c₂n   for n > 1
              T(n/2) = 2 T(n/4)+c₂n/2 - so plug it in
T(n) = 2[ 2 T(n/4)+c₂n/2 ] + c₂n   = 4T(n/4) + c₂n + c₂n = 4T(n/4) + 2c₂n
               T(n/4) = 2 T(n/8)+c₂n/4 - so plug it in
T(n) = 4 [ 2 T(n/8)+c₂n/4 ] + 2c₂n = 8T(n/8) + c₂n + 2c₂n = 8T(n/8) + 3c₂n
               T(n/8) = 2 T(n/16)+c₂n/8 - so plug it in
T(n) = 8 [ 2 T(n/16)+c₂n/8 ] + 3c₂n = 16T(n/16) + c₂n + 3c₂n = 16T(n/16) + 4c₂n
...
T(n) = 2^k T(n/2^k) + k*n c₂
as 2^k approaches n
T(n) < nc₁ + n*logn c₂

Verify using proof by induction

THEOREM:
T(n)    <    c₁                 for n < 1
                    2 T(n/2)+c₂n   for n > 1
has a closed form equation of T(n) < c₁n + c₂ nlogn

PROOF: By induction ( surprise!)

Base: T(n) < c₁n + c₂ nlogn so T(1) < c₁ + 0 = c₁
The recurrance relation states T(n)  < c₁ for n < 1; so T(1) < c₁
OK .

Induction hypothesis: Assume THM is true: T(n) < c₁n + c₂ nlogn for all n < n'.

Induction step:

Suppose n = n' + 1

then, T (n) < 2 T(n/2)+c₂n   for n > 1 (by definition of T(n))

since n/2 < n', by induction hypothesis, T (n/2) = c₁n/2 + c₂ n/2log(n/2)

Ok, let's look at T(n) again, Remember definition, T(n) < 2T (n/2) + c₂n so use inductive hypothesis on T(n/2)

T (n) < 2(c₁n/2 + c₂n/2 log n/2) + c₂n

< c₁n + c₂n(log n - 1) + c₂n

< c₁n + c₂nlog n

By induction, theorem is true for all n.

One could verify that it is O(nlogn)

DEFN.: f(n) = 0(g(n)) iff there exist two positive constants c and n₀ such that f(n) < c* g(n) for all n > n₀.

Is it was O(n)?

The answer is no and the proof is as follows (using the def. of Big O as specified)
Assume it is. We need to show:
c₁n + c₂nlog n < c₃n for some c₃ and all n > n₀
divide by n
c₁ + c₂log n < c₃
subtract c₁ and divide by c₂
log n < (c₃ - c₁)/ c₂
No matter what c₃ and n₀ we choose, log n will eventually grow greater as n gets large.
Contradiction, hence the algorithm is NOT O(n)