The master method - why can t it solve T(n) = 4*T(n/2) + (n^2)/logn?
I realize it can solve recurrences of type T(n) = aT(n/b) + f(n)
On MIT OCW they mentioned that it couldn t solve the above recurrence though. Can someone provide an explanation as to why?
Answer for T(n/2) + (n^2)/logn:
Case 1 does not apply because f(n) != O(n^-e) for any positive e.
Case 2 does not apply because f(n) != Θ(log^k(n)) for any k >= 0
Case 3 does not apply,
f(n) = Ω(n^e) for e = 1, BUT
a*f(n/b) <= c*f(n) for no c<1 (works out that c >= 2)
So we can t apply any case. Beyond this I m no good really - and again I m not 100% on this answer.
The following was prior to this edit, and assumed the question was with regards to T(n) = T(n/2) + n^(2logn) I m fairly sure that it is case 3 of the theorum.
Case 1 does not apply because f(n) != O(n^-e) for any positive e.
Case 2 does not apply because f(n) != Θ(log^k(n)) for any k >= 0
Case 3 does apply,
a*f(n/b) <= c*f(n) for some c<1 (works out that c >= 0.5)
and f(n) = Ω(n^e) for e = 1
I may be wrong so check it and let me know!
f(n)=(n^2)/logn and n^(log a/log b) . Compute the difference between the above two functions.
ratio= (n^2/log n)/(n^2)
The ratio turns out to be logarithmic. This recurrence relation falls in to the gap between case 2 and case 3. So Masters theorem is not applicable for this recurrence relation.
Masters theorem is applicable when the difference between the two functions stated above is polynomial.
its because in all the mentioned three cases you can t justify the positive asymptotic nature. which means when n->infinity n^2/lg(n) -> infinity, that simply implies n^e = w(lg(n)), Which can be paraphrased as "the function can not be contained" no upper bound exists for dividing and conquering procedures.
It seems to be the 3rd case as f(n) is greater but it should also satisfy the regularity condition (af(n/b)<=cf(n) for some c in(0,1)). Here the function is not satisfying the regularity condition so master method fails here
If I have an algorithm which is comprised of (let s say) three sub-algorithms, all with different O() characteristics, e.g.: algorithm A: O(n) algorithm B: O(log(n)) algorithm C: O(n log(n)) How do ...
I m using Electro in Lua for some 3D simulations, and I m running in to something of a mathematical/algorithmic/physics snag. I m trying to figure out how I would find the "spin" of a sphere of a ...
There s a (relatively) new sort on the block called Timsort. It s been used as Python s list.sort, and is now going to be the new Array.sort in Java 7. There s some documentation and a tiny Wikipedia ...
As a learning experience I recently tried implementing Quicksort with 3 way partitioning in C#. Apart from needing to add an extra range check on the left/right variables before the recursive call, ...
Given a 10 digit Telephone Number, we have to print all possible strings created from that. The mapping of the numbers is the one as exactly on a phone s keypad. i.e. for 1,0-> No Letter for 2->...
I have a directed graph and my problem is to enumerate all the minimal (cycles that cannot be constructed as the union of other cycles) directed cycles of this graph. This is different from what the ...
Given an array of integers arr = [5, 6, 1]. When we construct a BST with this input in the same order, we will have "5" as root, "6" as the right child and "1" as left child. Now if our input is ...
I was trying to speed up a certain routine in an application, and my profiler, AQTime, identified one method in particular as a bottleneck. The method has been with us for years, and is part of a "...