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

algorithm, big-o

Solution

Draw a recursion tree:

height of the tree will be log n

cost at each level will come out to be constant times n

Hence the total cost will be O(nlogn). http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/RecursionTree.htm

And you can always prove it by induction if you want.

Problem

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)`?

Original source