Analysis of Algorithms - Master Theorem

http://www.geeksforgeeks.org/analysis-algorithm-set-4-master-method-solving-recurrences/

Master Method is a direct way to get the solution. The master method works only for following type of recurrences or for recurrences that can be transformed to following type.

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

There are following three cases:
1. If f(n) = Θ(nc) where c < Logba then T(n) = Θ(nLogba)

2. If f(n) = Θ(nc) where c = Logba then T(n) = Θ(ncLog n)

3.If f(n) = Θ(nc) where c > Logba then T(n) = Θ(f(n))

How does this work?
Master method is mainly derived from recurrence tree method. If we draw recurrence tree of T(n) = aT(n/b) + f(n), we can see that the work done at root is f(n) and work done at all leaves is Θ(nc) where c is Logba. And the height of recurrence tree is Logbn

In recurrence tree method, we calculate total work done. If the work done at leaves is polynomially more, then leaves are the dominant part, and our result becomes the work done at leaves (Case 1). If work done at leaves and root is asymptotically same, then our result becomes height multiplied by work done at any level (Case 2). If work done at root is asymptotically more, then our result becomes work done at root (Case 3).

Examples of some standard algorithms whose time complexity can be evaluated using Master Method 
Merge Sort: T(n) = 2T(n/2) + Θ(n). It falls in case 2 as c is 1 and Logba] is also 1. So the solution is Θ(n Logn)

Binary Search: T(n) = T(n/2) + Θ(1). It also falls in case 2 as c is 0 and Logba is also 0. So the solution is Θ(Logn)

Notes: 
1) It is not necessary that a recurrence of the form T(n) = aT(n/b) + f(n) can be solved using Master Theorem. The given three cases have some gaps between them. For example, the recurrence T(n) = 2T(n/2) + n/Logn cannot be solved using master method.

2) Case 2 can be extended for f(n) = Θ(ncLogkn)
If f(n) = Θ(ncLogkn) for some constant k >= 0 and c = Logba, then T(n) = Θ(ncLogk+1n)

The master method applies to recurrences of the form

          T(n) = a *T(n/b) + f(n)

where a>=1, b>1, and f is asymptotically positive.

Example:

 Ideas of master theorem

CASE 1: The weight increases geometrically from the root to the leaves. The leaves hold a constant fraction of the total weight.

CASE 2: (k = 0) The weight  is approximately the same on each of the logbn levels

CASE 3: The weight decreases geometrically from the root to the leaves. The root holds a constant fraction of the total weight.

http://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/lec20.html

Recursion Trees

A recursion tree is useful for visualizing what happens when a recurrence is iterated. It diagrams the tree of recursive calls and the amount of work done at each call.

For instance, consider the recurrence

T(n) = 2T(n/2) + n².

The recursion tree for this recurrence has the following form:

In this case, it is straightforward to sum across each row of the tree to obtain the total work done at a given level:

This a geometric series, thus in the limit the sum is O(n²). The depth of the tree in this case does not really matter; the amount of work at each level is decreasing so quickly that the total is only a constant factor more than the root.

Recursion trees can be useful for gaining intuition about the closed form of a recurrence, but they are not a proof (and in fact it is easy to get the wrong answer with a recursion tree, as is the case with any method that includes ''...'' kinds of reasoning). As we saw last time, a good way of establishing a closed form for a recurrence is to make an educated guess and then prove by induction that your guess is indeed a solution. Recurrence trees can be a good method of guessing.

Let's consider another example,

T(n) = T(n/3) + T(2n/3) + n.

Expanding out the first few levels, the recurrence tree is:

Note that the tree here is not balanced: the longest path is the rightmost one, and its length islog_3/2 n. Hence our guess for the closed form of this recurrence is O(n log n).

http://pfmiles.github.io/blog/algo-class-week2-notes-master-method/

Quiz and Practice
http://www.csd.uwo.ca/~moreno//CS424/Ressources/master.pdf
1. T (n) = 3T (n/2) + n
2 =⇒ T (n) = Θ(n^2) (Case 3)
2. T (n) = 4T (n/2) + n
2 =⇒ T (n) = Θ(n^2log n) (Case 2)
3. T (n) = T (n/2) + 2^n =⇒ Θ(2^n) (Case 3)
4. T (n) = 2nT (n/2) + n
n =⇒ Does not apply (a is not constant)
5. T (n) = 16T (n/4) + n =⇒ T (n) = Θ(n^2) (Case 1)
6. T (n) = 2T (n/2) + n log n =⇒ T (n) = n (logn)^2 (Case 2)
7. T (n) = 2T (n/2) + n/ log n =⇒ Does not apply (non-polynomial difference between f(n) and nlogb a)
8. T (n) = 2T (n/4) + n^0.51 =⇒ T (n) = Θ(n^0.51) (Case 3)
9. T (n) = 0.5T (n/2) + 1/n =⇒ Does not apply (a < 1)

10. T (n) = 16T (n/4) + n! =⇒ T (n) = Θ(n!) (Case 3)
http://geeksquiz.com/algorithms-analysis-of-algorithms-recurrences-question-11/

Consider the following recurrence.

T(n) = T() + 

What is the value of recurrence?

(A) 

Change of variables: let m = lg n. Recurrence becomes S(m) = S(m/2) + theta(lgm). Case 2 of master’s theorem applies, so T(n) = theta( (log Log n) ^ 2).
http://geeksquiz.com/algorithms-analysis-of-algorithms-recurrences-question-10/
Consider the following recurrence
T(n) = 3T(n/5) + lgn * lgn
 By Case 1 of the Master Method, we have T(n) = Theta(n ^ (log5(3)) ). [^ is for power]

todo: http://geeksquiz.com/tag/analysis-of-algorithms-recurrences/