# Recurrence > [!summary] Definition A **recurrence** is an equation that describes a > [[function]] in terms of its value on other, typically smaller, arguments. - Note the difference from [[recursion]]. - Recurrence relation: A [[function]] whose definition depends on itself. - _[[algorithm|Algorithmic]]_ recurrence, and its _threshold_ $n_0$, so that - $T(n) = \Theta(1)$ for $n < n_0$, and - Every path of recursion terminates in a defined base case within a finite number of recursive invocations for $n \ge n_0$. - Approximations - The complexity does not depend on the threshold as long as it's large enough to cover all base cases. - Ignoring floors and ceilings ## Examples - Architectures: [[hypercube]], mesh, complete [[binary-tree|binary trees]]. - [[binary-multiplication]] - [[fibonacci]] ## Solution Solving the recurrence relationship to get _closed-form solution_. (Or just an asymptotic bound) When can the floors and ceilings be ignored? Refer to [[akra-bazzi|Akra-Bazzi recurrence]]. ### Substitution - Guess the right form first, plug the bound back in to [[induction|inductively]] prove it - Subtracting a lower-order term from the guess may help, e.g. $T(n) \le cn - d$. - Avoid using [[asymptotic-notation]] in the substitution proof, keep the basic definition, as the constant behind the anonymous notation is unclear. Prove the **exact** [[induction|inductive]] hypothesis! - For the guesses made - If $c$ doesn't exist, the guess it too low - If $c\to0$ as $n\to\infty$, the guess is too high ### Recursion-Tree - or iterative method - Plug the equation back to itself, all the way down to base case, and derive the solution - see [[binary-multiplication#Iterative Solution]] - Unsure of the leaves? Write another recurrence $L(n)$ to characterize the number of leaves! ### Master Method Based on the [[master-theorem]]. ### Akra-Bazzi method See [[akra-bazzi]]. ### [[generating-function|Generating Function]] See [[fibonacci]].