## Oct 10, 2018

### [HDGEM] Algorithms: The master theorem

The master theorem concerns recurrence relations of the form:
${\displaystyle T(n)=a\;T\!\left({\frac {n}{b}}\right)+f(n)}$ where ${\displaystyle a\geq 1{\mbox{, }}b>1}$
In the application to the analysis of a recursive algorithm, the constants and function take on the following significance:
• n is the size of the problem.
• a is the number of subproblems in the recursion.
• n/b is the size of each subproblem. (Here it is assumed that all subproblems are essentially the same size.)
• f (n) is the cost of the work done outside the recursive calls, which includes the cost of dividing the problem and the cost of merging the solutions to the subproblems.

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))

--
Posted By Blogger to HDGEM at 3/07/2017 10:59:00 AM