Analysis Of Algorithm #
There are many ways to analyze recurrence relations like
- Master Theorem
- Substitution Method
- Recurrence tree method
Master Theorem #
Master Theorem presents a framework and formula using which solutions to many recurrence relations can be obtained very easily.
Almost all recurrences of type \(T(n) = aT(n/b) + f(n)\) can be solved easily by doing a simple check and identifying one of the three cases provided by the theorem.
By comparing \( n ^{\log_b a} \) (the number of leaves) with \(f(n)\) , one can decide upon the time complexity of the algorithm.
The master theorem provides a solution to recurrence function of the form
Let
\(T(n)\)
be a monotonically increasing function that satisfies:
\(T(n) = a T(n/b) + f(n)\)
\(T(1) = c\)
where
\(a \ge 1, b \ge 2, c>0\)
.
If
\(f(n)\)
is
\(\Theta(n^d)\)
where
\(d \ge 0\)
then
\(
x = \begin{cases}
a &\text{if } b \\
c &\text{if } d
\end{cases}
\)
Continued….