thermis Posted December 9, 2003 Share Posted December 9, 2003 t(n) = 2 t(n/2) + n log n should fit in the third rule of master method, since n ^ lg 2 Why they say it doesn't fit the rule 3 of master theory !? Quote Link to comment Share on other sites More sharing options...
dionysus Posted December 9, 2003 Share Posted December 9, 2003 t(n) = 2 t(n/2) + n log n Good question thermis. I was wondering too. The solution that is derived is O(n log n log n). This can be derived using expansion: t(n) = 2 t(n/2) + n log n = 2 (2 t(n/4) + n/2 log n/2) + n log n = 2^k t (n/2^k) + n log (n/2^{k-1}) + n log (n/2^{k-2}) + ... + n log (n/2) + n log n = 2^k t (n/{2^k}) + n (log n + log n/2 + ... log (n/2^{k-1})) Plug k = log_2 n, we get, = n + n (log n log n - (log n) (log n - 1)/2 log 2) = O( n log n log n). With the master method, although ,the solution that is acceptable is O(n log n) which isn't correct! Quote Link to comment Share on other sites More sharing options...
dionysus Posted December 9, 2003 Share Posted December 9, 2003 t(n) = 2 t(n/2) + n log n should fit in the third rule of master method, since n ^ lg 2 Why they say it doesn't fit the rule 3 of master theory !? This is a great question and it feels good to have figured it out! The third rule of the master theorem says that if f(n) belongs to Big-Omega of (n^{log_b a} + epsilon) for some epsilon > 0 and a f(n/b) Now let us examine the two conditions under which this rule applies. In our case, T(n) = 2 T(n/2) + n log n, we have f(n) = n log n, a = 2 and b = 2. So log_b a = log_2 2 = 1. So the first condition is: [*] f(n) belongs to Big-Omega (n^{1 + epsilon}). [*] n log n belongs to Big-Omega (n^{1 + epsilon}). [*] log n belongs to Big-Omega (n^{epsilon}) (cancelling out n^1 on both sides) [*] but log n does not belong to Big-Omega (n^{epsilon}) for even a small epsilon, since log n grows logarithmically and n^{epsilon} atleast grows polynomially. So, we notice that the first condition of the master theorem is not satisfied. This is a subtle point, but well brought out thermis! Quote Link to comment Share on other sites More sharing options...
thermis Posted December 9, 2003 Author Share Posted December 9, 2003 oh I get it, thnks. Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.