Master Theorem

Master Theorem

$$ T(n) = aT(rac{n}{b})+f(n) $$

where a≥1,b≥1 be constant and f(n) be a function

Let T(n) is defined on non-negative integers by the recurrence

• n is the size of the problem
• a is the number of sub problems in the recursion
• rac{n}{b} is the size of each sub problem (Here it is assumed that all sub problems are essentially the same size)
• f(n) is the time to create the sub problems and combine their results in the above procedure

There are following three cases:

1. If f(n)=Theta(n^c) where c < log_bacolor{red}{T(n)=Theta(n^{log_ba})}
2. If f(n)=Theta(n^c) where c=log_ba then color{red}{T(n)=Theta(n^clogn)}
3. If f(n)=Theta(n^c) where c>log_bacolor{red}{T(n)=Theta(f(n))}

Indamissible equations

$$ T(n)=color{red}{2^n}T(rac{n}{2}) + n $$

a is not constant. The number of subproblems should be fixed

$$ T(n)=color{red}{0.5}{T(rac{n}{2})+n} $$

a< 1

$$ T(n)=16T(rac{n}{2})color{red}{-n^2} $$

f(n) which is the combination time is not positive