How to get O(nlogn) from T(n) = 2T(n/2) + O(n)

Question

I want to calculate O(n log(n)) without using the master theorem.

Does anyone know a mathematical way of calculating O(n log(n)) from the recursive formula T(n) = 2T(n/2) + O(n)?

Answer 1

Notice the pattern (simplified a bit, better would be to keep O(n) rather than n):

T(n) = 2T(n/2) + n
     = 2(2T(n/4) + n/2) + n  = 4T(n/4) + n + n  = 4T(n/4) + 2n
     = 4(2T(n/8) + n/4) + 2n = 8T(n/8) + n + 2n = 8T(n/8) + 3n
     = 8(2T(n/16) + n/8)+ 3n = 8T(n/16)+ n + 3n = 16T(n/16) + 4n
     ...                                        = 32T(n/32) + 5n
     ...
                                                = n*T(1) + log2(n)*n
                                                = O(n*log2(n))