Q1Design and Analysis of Algorithms
Question
2 marks
Define Recurrence Relation.
Answer
A recurrence relation defines a sequence where each term is a function of one or more previous terms.
A Recurrence Relation is an equation that defines each element of a sequence in terms of one or more of its preceding elements. In algorithm analysis, it expresses the running time T(n) of a recursive algorithm in terms of the running time on smaller inputs.
Example: T(n) = T(n-1) + 1 (recursive linear scan), T(n) = 2T(n/2) + n (Merge Sort), T(n) = T(n-1) + T(n-2) (Fibonacci). Solving recurrences (Substitution, Recursion Tree, or Master Theorem) gives the closed-form time complexity.