How to get O(nlogn) from T(n) = 2T(n/2) + O(n)
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))
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.