Saturday, 21 March 2015

Master theorem for complexity analysis

Master theorem is used to analyze complexity of many problems in divide and conquer category.
Master theorem deals with recurrence relations in the form:

T(n)= aT(n/b)+f(n)
where:
n is size of original problem
a is number of sub-problems
n/b size of sub-problems(assuming sub-problems of equal size)

f(n) is the time required to conquer(dividing or merging) the sub-problems;

such as merging in merge sort or finding pivot in quick sort</em>

There are 3 cases to solve such kind of recurrences:
In each of three cases we compare f(n) with (n logba). Polynomially larger of these functions determines solution.

Case 1:
If f(n) = O( nc ) where c < logba
then solution becomes T(n) = θ(n logba)

In first case, comparison states that (n logba) is larger than f(n),hence solution θ(n logba)

For example:
T(n) = 9T(n/3)+1000n2
a=9, b=3, f(n)=n2 (leaving constant terms)
n logba = n log39 = n3 which is polynomially greater than n2.
Hence solution T(n) = θ(n3)

Case 2:
 if f(n) = θ(n log b a )
then solution becomes T(n) = θ(n logba logn)
In second case, comparison states that (n logba) is equal to f(n), we multiply f(n) by logarithmic factor hence solution θ(n logba logn)

For example:
T(n) = T(n/2)+c (Binary search)
a=1, b=2, f(n)=c (constant)
n logba = n log21 = n0 = 1 which is equal to f(n).
Hence solution T(n) = θ(logn)

Case 3:
if f(n) = Ω( nc ) where c > logba
and it is also true that af(n/b) <= kf(n) for some constant k < 1,
and sufficiently large n.
then solution becomes T(n) = θ( f(n) )

In third case comparison states that (n logba) is smaller than f(n).
hence solution θ( f(n) )

For example:
T(n) = 2T(n/2)+10n2 a=2, b=2, f(n)=n2 (leaving constant terms)
n logba = n log22 = n which is polynomially smaller than n2.
Hence solution T(n) = θ(n2)  

Facts :
Master theorem doesn't apply if function is not polynomially large enough to determine solution.
 eg : T(n) = 2T(n/2)+nlogn here a=2,b=2
f(n) = n logn;
nlogba = n;
so f(n) is greater than nlogba but not polynomially large enough, its large by a factor of logarithm hence can't determine solution.