📘 Recurrence (Recurrence Relations)

A Recurrence or Recurrence Relation is an equation that defines a function or running time in terms of its value for smaller inputs.

In simple words:

👉 A recurrence expresses the time complexity of a recursive algorithm.

An algorithm that calls itself several times gives rise to a recurrence.

📌 Why Recurrence is Important?

Used to analyze recursive algorithms
Helps find time complexity of Divide & Conquer algorithms
Essential for algorithms like Merge Sort, Quick Sort, Binary Search
Important for GATE, university exams, placements

📘 General Form of Recurrence

Most recurrence relations appear in the form:

T(n) = aT(n/b) + f(n)

Where:

T(n) → time complexity for input size n
a → number of recursive calls
n/b → size of each subproblem
f(n) → non-recursive work (splitting, combining, loops)

Example:
Merge Sort: T(n) = 2T(n/2) + n

📌 Examples of Recurrences

Here are the most common recurrence relations used in DSA:

1. T(n) = T(n – 1) + O(1)

Example: Linear recursion
Solution: T(n) = O(n)

2. T(n) = T(n – 1) + n

Example: Sum of first n numbers
Solution: O(n²)

3. T(n) = 2T(n – 1) + O(1)

Solution: O(2ⁿ)

4. T(n) = T(n/2) + O(1)

Example: Binary Search
Solution: O(log n)

5. T(n) = 2T(n/2) + O(n)

Example: Merge Sort
Solution: O(n log n)

6. T(n) = 2T(n/2) + O(1)

Solution: O(n)

📘 Methods to Solve Recurrences

There are three main methods to solve recurrences:

1. Substitution Method (Iterative Method)

Expand the recurrence repeatedly until a pattern appears.

Example:

T(n) = T(n/2) + n
Solution steps:

T(n) = T(n/2) + n
T(n/2) = T(n/4) + n/2
T(n/4) = T(n/8) + n/4
…
Add all terms:

T(n) = n + n/2 + n/4 + … + 1
This is a GP = O(2n) = O(n)

2. Recursion Tree Method

Draw a tree to visualize work done at each level.

Example:

T(n) = 2T(n/2) + n

Recursion Tree:

Level 0 → n
Level 1 → 2 × (n/2) = n
Level 2 → 4 × (n/4) = n
…
Height = log n
Total work = n × log n
👉 T(n) = O(n log n)

3. Master Theorem

Fastest method for solving recurrences of type:

T(n) = aT(n/b) + f(n)

Master Theorem has three cases:

Case 1:

If
f(n) = O(nᶜ) where c < logᵦa

Then: T(n) = Θ(n^(logᵦa))

🔹 Example:
T(n) = 2T(n/2) + 1
Here a = 2, b = 2
logᵦa = log₂2 = 1
f(n) = O(1) → c = 0 < 1
Answer: O(n)

Case 2:

If
f(n) = Θ(nᶜ) where c = logᵦa

Then: T(n) = Θ(nᶜ log n)

🔹 Example:
T(n) = 2T(n/2) + n
Here a = 2, b = 2
log₂2 = 1
f(n) = n → c = 1
Answer: O(n log n)

Case 3:

If
f(n) = Ω(nᶜ) where c > logᵦa
and f(n) satisfies regularity condition

Then: T(n) = Θ(f(n))

🔹 Example:
T(n) = 2T(n/2) + n²
Here log₂2 = 1
c = 2 > 1
Answer: O(n²)

📘 Standard Recurrence Solutions (Must Memorize)

Recurrence	Solution
T(n) = T(n–1) + 1	O(n)
T(n) = T(n–1) + n	O(n²)
T(n) = 2T(n/2) + 1	O(n)
T(n) = 2T(n/2) + n	O(n log n)
T(n) = 2T(n/2) + n²	O(n²)
T(n) = T(n/2) + 1	O(log n)
T(n) = T(n/2) + n	O(n)
T(n) = 3T(n/2) + n	O(n^(log₂3)) ≈ O(n^1.58)

📘 Example Problems (Exam Style)

Q1: Solve T(n) = T(n – 1) + n

Solution:

T(n) = n + (n–1) + … + 1
= (n(n+1))/2
👉 O(n²)

Q2: Solve T(n) = T(n/2) + n²

Here a = 1, b = 2
log₂1 = 0
f(n) = n² → c = 2 > 0
Case 3 of Master Theorem
👉 O(n²)

🎯 Summary (For Exams)

Recurrence expresses the running time of recursive algorithms.
Main solving techniques:
✔ Substitution Method
✔ Recursion Tree
✔ Master Theorem
Most common recurrence:
✔ T(n) = 2T(n/2) + n → O(n log n)
✔ T(n) = T(n/2) + 1 → O(log n)
✔ T(n) = T(n–1) + n → O(n²)