Geek asks and answers

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

Hi, I am learning an algorithm and I am asking a question about getting O (nlogn) without using the main theorem.

I'm having trouble getting O (nlogn) ..

Does anyone know what mathematical methods are to get O (nlogn) from T (n) = 2T (n / 2) + O (n)?

thank

+3
source share
2 answers

Draw a recursion tree:

tree height will be log n

the value at each level will be equal to constant times n

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

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

+3
source

( , O(n), 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))
+8

More articles:


All Articles