🔗
Recurrence Relations
★★★☆☆High School
📖Definition
A recurrence relation defines sequence terms using previous terms. It's essential for analyzing recursive algorithm complexity.
📐Formulas
aₙ = a_n-1 + a_n-2
Fibonacci recurrence
T(n) = 2T(n/2) + n
Merge sort recurrence
aₙ = r · a_n-1 ⇒ aₙ = a₁ · r^n-1
Geometric sequence
✏️Examples
예제 1
If a₁ = 1, aₙ = 2aₙ₋₁ + 1, find the first 5 terms.
⚡Applications
Algorithm Analysis
Time complexity
Dynamic Programming
Optimization problems
Finance
Compound interest
🔗Related Documents
→Prerequisites
←Next Topics
↔Related
#점화식#재귀#recurrence#recursion