In the Master Theorem, cases 1 & 3 you have if f(n) = O(log b of a-e) in case 1, I wondered why one has to subtract the constant e there?
In the third case of the master theorem one has to add a constant... Why is that so?
What is the constant based on?
You might think of it this way - lets take the third case as an example:
f(n) = O(n^(log(b a) + e)) for e < 0 (The log is not of (a - e), but rather it s (log in base b of a) - e)
What does this mean?
Lets establish one thing first: The entire blob at the right side - O(n^(log(b a))). This is, in essence, the asymptotic behaviour of the T(n) function, without taking into account the f(n) part of it.
This part is not perfectly intuitive, but think about it, and you ll see its correct. (Just calculate some values for f(n) = O(1) and you ll see I m right. Since nonexistant f(n) is, for all intents and purposes, O(1).)
So, given that, we look at the e. What does the e do? It s lower than zero for sure, we know that thanks to the constraints we put on it, so that means the e will lower the asymptotic "class" (as in, n^2, log n, etc.) when put in the equation. In other words, if you can lower the asymptotic class of the aT(n/b) part and make it equal to f(n), then that means aT(n/b) is asymptotically bigger than f(n), and we act accordingly.
What this means, and what the master method is all about, is solving the following: O(T(n) - f(n)) = O(f(n)).
Lets look at the generic form the master method is based upon:
T(n) = aT(n/b) + f(n)
The aT(n/b) part, is in essence the loop. The thing that decides how many iterations we will have. The right part, is the body of the loop. The actual work done. If the right side is asymptotically weak to the left side, than the right side matters less, and we have some lovely formulas to decide the asymptotic behaviour if its weaker, equal or bigger. We substract or add the e as I explained above, to find out if it s bigger, smaller or equal.
It s a bit hard for me to explain these kinds of things in text and not in my native language, I hope it was understood.
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 "...
