Understanding how to write a recurrence relation for a given piece of code is crucial for analyzing its computational complexity, especially for recursive algorithms. Recurrence relations express the overall complexity of an algorithm in terms of the complexity of its subproblems. This article will delve into the steps involved in deriving such relations, illustrated with examples, and will provide additional techniques and considerations to account for complete analysis.

Understanding Recurrence Relations

A recurrence relation is an equation or inequality that describes a function in terms of its value at smaller inputs. It's a tool often employed in analyzing recursive functions, where the main problem is solved using solutions to subproblems, making it suitable for algorithms such as Merge Sort, Fibonacci sequence calculations, or Dynamic Programming approaches.

Typical Form of a Recurrence Relation

A recurrence relation typically has the following form:

$$T(n) = a \cdot T\left( \frac{n}{b} \right) + f(n)$$

Where: • $T(n)$ is the time complexity for solving a problem of size $n$. • $a$ is the number of subproblems in the recursion. • $b$ is the factor by which the subproblem size is reduced in each call. • $f(n)$ is the cost of the work done outside the recursive calls, often involving dividing the problem or merging results from subproblems.

Steps to Derive a Recurrence Relation

Let's break down the process of deriving a recurrence relation using the Merge Sort algorithm as an example.

Example: Merge Sort

Merge Sort is a classic divide-and-conquer algorithm. The function can be described by repeatedly splitting the array in half, recursively sorting each half, and then merging the sorted halves.

• Let $n$ be the size of the array `arr`. • The array is split into two halves, hence $a = 2$. • Each recursive call processes half of the array, hence the size becomes $\frac{n}{2}$, meaning $b = 2$. • The `merge` operation is applied outside the recursive calls. Merging two halves takes linear time $O(n)$. • Combine these components into the recurrence:

• Here the problem size is $n$. • There is one recursive call, so $a = 1$. • Each recursive call reduces the problem size by 1, so $b = n - (n - 1) = n - 1$. • The multiplication `n * factorial(n-1)` is a constant time operation $O(1)$. • The recurrence relation is: • Guess a solution and use mathematical induction to prove. • Directly applies to relations of the form $T(n) = a \cdot T\left( \frac{n}{b} \right) + f(n)$. • Visualizes the recurrence as a tree and determines the total work by calculating the cost at each level. • Base Cases: Ensure to account for trivial cases (e.g., $T(1)$ or $T(0)$) which terminate the recursion. • Iterative Equivalents: Sometimes deriving recurrence from the iterative processes can also facilitate understanding, especially if the algorithm was initially iterative. • Multiple Recursions: Some complex algorithms involve double recursion (e.g., Fibonacci), necessitating combinatorial reasoning or deeper insights into their geometric growth or decay patterns.