Jump to content
Urch Forums

2 t(n/2) + n log n doesn't fit in master method ?


thermis

Recommended Posts

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!

Link to comment
Share on other sites

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!

 

 

 

 

 

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...