4.3-6 Show that the solution to T(n) = 2T(\lfloor (n/2) \rfloor + 17)+ n is O(n lg n). let $T(n) \leq c(n-34) lgn - n $ $$ T(n) = 2c(n/2 -34+17) lg(n/2+17) - 2n + n $$ $$ T(n) = c(n -34) lg(n/2+17) - n $$ $$ T(n) = c(n -34) lg(n/2+17) - n < c(n-34)lg n -n $$ the above eq is less than $ c(n-34)lg n -n $ becoz n/2+17 < n.
Thursday, December 20, 2012
4.3-6
4.3-6 Show that the solution to T(n) = 2T(\lfloor (n/2) \rfloor + 17)+ n is O(n lg n). let $T(n) \leq c(n-34) lgn - n $ $$ T(n) = 2c(n/2 -34+17) lg(n/2+17) - 2n + n $$ $$ T(n) = c(n -34) lg(n/2+17) - n $$ $$ T(n) = c(n -34) lg(n/2+17) - n < c(n-34)lg n -n $$ the above eq is less than $ c(n-34)lg n -n $ becoz n/2+17 < n.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment