Recurrence Relation

/rɪˈkɜː.rəns rɪˈleɪ.ʃən/ · Noun · Development · Origin: 1202

Definitions

  1. Recurrence Relation is a mathematical equation that defines a sequence of values where each term is expressed as a function of one or more preceding terms. In computer science, recurrence relations are the primary tool for analyzing the time complexity of recursive algorithms. When a recursive function divides a problem into subproblems, the recurrence describes how the total work relates to the work done on subproblems. The classic example is the Merge Sort recurrence T(n) = 2T(n/2) + O(n), expressing that the algorithm splits the input in half (two subproblems of size n/2) and does linear work to merge results. The Master Theorem provides a formula for solving many common recurrences of the form T(n) = aT(n/b) + f(n). Other solving methods include substitution (guessing and proving by induction), recursion trees (visualizing the work at each level), and the Akra-Bazzi method for more general cases. The Fibonacci sequence F(n) = F(n-1) + F(n-2) is perhaps the most famous recurrence relation, appearing throughout computer science and mathematics.

    In plain English: A formula where each value depends on the previous values (like Fibonacci). It's how we figure out how fast recursive algorithms run.

    Example: "The recurrence for merge sort is T(n) = 2T(n/2) + n — plug it into the Master Theorem and you get Θ(n log n)."

Related Terms