How To Solve Recurrence Relations
What is a recurrence relation ? If you search “Recurrence Relation” on Google.com you might get something back like. “ In mathematics, a recurrence relation is an equation that recursively defines a sequence or multidimensional array of values, once one or more initial terms are given: each further term of the sequence or array is defined as a function of the preceding terms.”
Recurrence relation in computer science is just an equation that defines itself.
It has one or more base cases also known as non-recursive output, and a recursive case, input for which a function or algorithm or program calls itself. It can easily describe the run-time or space(memory) needed of a recursive algorithm or program.
Example of Recurrence Relation:
T(n) = T(n/3) + 100
T(2) = 3
How To Solve A Recurrence Relation Running Time ?
1. Use The Master Theorem
To solve a recurrence relation running time you can use many different techniques. One popular technique is to use the Master Theorem also known as the Master…
