Recurrence Relation Method

The Recurrence Relation Method allows us to express the time complexity of a recursive algorithm as a mathematical equation, or recurrence relation, based on the size of the input.

Recurrence relations are equations that express the time complexity of a recursive function in terms of the function itself. This method is useful for algorithms where each recursive call breaks the problem down into smaller subproblems until a base case is reached.

Example: Factorial Function

Let’s analyze the time complexity of a recursive function that calculates the factorial of a number, n!. The factorial of n is defined as the product of all positive integers up to n. We can calculate it using a recursive approach as shown below.

Factorial Code

class Solution {

  public int factorial(int n) {
    // Base case: factorial of 0 or 1 is 1
    if (n == 0 || n == 1) {
      return 1;
    } else {
      // Recursive call: factorial(n) = n * factorial(n-1)
      return n * factorial(n - 1);
    }
  }

  public static void main(String[] args) {
    int number = 5; // Example number

    Solution solution = new Solution();
    int result = solution.factorial(number);

    System.out.println("Factorial of " + number + " is: " + result);
  }
}

• Base Case: If n is 0 or 1, the function returns 1. This is the stopping condition, preventing infinite recursion.
• Recursive Case: For values of n greater than 1, the function calls itself with n - 1, multiplying the result by n each time.

Setting Up the Recurrence Relation

To analyze the time complexity of this recursive function, let’s set up a recurrence relation.

Let:

• represent the time complexity of calculating the factorial of .

The recurrence relation for factorial(n) is:

Here:

• : Represents the time complexity of the recursive call, where the function computes factorial(n - 1).
• : Represents the constant time needed for the multiplication operation .

Solving the Recurrence Relation

Let’s expand this relation step-by-step:

Expanding these terms recursively until we reach the base case, :

Since is a constant, the total complexity of becomes:

The time complexity of the factorial function is , meaning the function requires linear time relative to the input size .

Binary Search Recurrence Relation Analysis

In the previous lesson, we found the time complexity of the binary search by using the recursion tree. Here, we will find the time complexity of the binary search algorithm using the Recurrence Relation Analysis.

In binary search, each recursive call reduces the search range by half. This halving process continues until the range is reduced to a single element, or the base case is reached. Let’s break down the time complexity of this algorithm by setting up a recurrence relation.

Binary Search

Here’s the Python code for binary search, along with comments explaining each step.

class Solution {
    public static int binary_search(int[] arr, int target, int low, int high) {
        // Base case: if the range is invalid, the target is not found
        if (low > high) {
            return -1;
        }

        // Find the middle index
        int mid = (low + high) / 2;

        // Check if the middle element is the target
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            // Recursive call to search in the right half
            return binary_search(arr, target, mid + 1, high);
        } else {
            // Recursive call to search in the left half
            return binary_search(arr, target, low, mid - 1);
        }
    }

    public static void main(String[] args) {
        int[] sortedArray = {1, 3, 5, 7, 9, 11, 13}; // Example sorted array
        int target = 7; // Target element to find

        Solution solution = new Solution();
        int index = solution.binary_search(sortedArray, target, 0, sortedArray.length - 1);

        if (index != -1) {
            System.out.println("Element found at index: " + index);
        } else {
            System.out.println("Element not found in the array.");
        }
    }
}

Setting Up the Recurrence Relation

To analyze the time complexity, let’s define:

• as the time complexity for binary search on an array of size .

Since each call reduces the search range by half, we can represent this in our recurrence relation as follows:

Where:

• : Represents the time complexity for a recursive call on half the original input size.
• : Represents the constant time taken to calculate the middle index and perform the comparison with the target.

Expanding the Recurrence Relation

To solve for , let’s expand the recurrence relation by substituting until we reach the base case:

The recursion stops when the input size is reduced to 1, so we set . Solving for , we get:

Thus, the recursion tree has levels.

Final Complexity Calculation

Since each level requires work and there are levels, the total time complexity of binary search is:

I just read a lesson on **Recurrence Relation Method** (DSA) and want to truly understand it. Explain Recurrence Relation Method from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Teach me **Recurrence Relation Method** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Quiz me on **Recurrence Relation Method** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Help me remember **Recurrence Relation Method** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.