Mathematical Analysis of Recursive Algorithms

What is a recurrence relation? How is it used to describe the efficiency of recursive algorithms?

A recurrence relation is an equation that recursively defines a sequence, where each term is described as a function of its preceding terms, rather than as a direct function of the index n.

To be well-defined, a recurrence relation must be paired with one or more base cases (or initial conditions) that specify the starting values.

For example, The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, ...) is defined by the recurrence relation:
F(n) = F(n - 1) + F(n - 2) for n > 1,
with initial conditions: F(0) = 0, F(1) = 1.

---

In algorithm analysis, recurrence relations are the primary tool for describing the time complexity of recursive algorithms. The structure of a recursive algorithm naturally leads to a recurrence relation.

A typical recurrence for an algorithm's runtime, T(n), consists of two parts:

1. Recursive Cost: The time taken to execute the recursive calls on smaller sub-problems.

2. Non-Recursive Cost: The time taken for work done within the function itself, such as dividing the problem or combining the results from sub-problems.

Solving the recurrence gives an explicit expression for the algorithm’s runtime in terms of the input size n. This, in turn, helps determine the algorithm's efficiency class, such as O(log n), O(n), O(n log n), O(n²), and so on.

Describe the general plan or steps for analyzing the time efficiency of recursive algorithms.

Analyzing the time efficiency of a recursive algorithm is a systematic process. The general plan involves these five steps:

1. Decide on an input size parameter: Choose a parameter (or parameters) that indicates the size of the input. For example, for the factorial function, n itself is a natural choice.

2. Identify the basic operation: Determine the operation within the algorithm that contributes most to the total running time. This is typically the most time-consuming operation in the algorithm's innermost loop. Example: In a recursive factorial algorithm, factorial(n) = n * factorial(n-1), the basic operation is the multiplication.

3. Check for input variation: Determine if the number of basic operations can change for different inputs of the same size n.

   • If the count is always the same (like for factorial or Merge Sort), you only need one analysis.
   • If the count can vary (like for Quicksort, depending on pivot choices), analyze the worst-case, average-case, and best-case scenarios separately.

4. Set up the recurrence relation: Formulate a recurrence relation for the number of times the basic operation is executed, T(n). This equation expresses T(n) in terms of its value on smaller inputs, along with a base case.

5. Solve the recurrence: Solve the recurrence relation to find a closed-form formula for the number of basic operations in terms of the input size n, or at least determine its order of growth

Set up and solve the recurrence relation for the time complexity of computing n! (factorial) using a recursive algorithm.

Page 96

To analyze the time complexity of the given recursive algorithm for computing n! (factorial), we follow a general plan for analyzing recursive algorithms.

The algorithm is:

ALGORITHM F(n)
//Computes n! recursively
//Input: A nonnegative integer n
//Output: The value of n!

if n = 0 
	return 1
else 
	return F(n - 1) * n

Here's the step-by-step analysis:

1. Decide on a parameter indicating an input’s size: The natural choice for the input size is n, the non-negative integer for which the factorial is being computed.

2. Identify the algorithm’s basic operation: The most frequently executed operation in this algorithm is multiplication (*). This occurs in the return F(n - 1) * n line.

3. Check whether the number of times the basic operation is executed can vary on different inputs of the same size: In this algorithm, for any given n > 0, there is always exactly one multiplication performed at each level of recursion (to multiply F(n-1) by n). The number of multiplications depends solely on the value of n, so there's no need to distinguish between worst-case, average-case, or best-case scenarios based on input specifics.

4. Set up a recurrence relation, with an appropriate initial condition, for the number of times the basic operation is executed: Let M(n) denote the number of multiplications performed by the algorithm for an input of size n.

   • For n > 0, F(n) calls F(n-1) and then performs one multiplication. Therefore, M(n) = M(n - 1) + 1.
   • For the base case, when n = 0, the algorithm returns 1 without performing any multiplications. Thus, the initial condition is M(0) = 0.

   Combining these, the recurrence relation is: M(n) = M(n - 1) + 1 for n > 0 and M(0) = 0

5. Solve the recurrence to ascertain the order of growth of its solution: We can solve this recurrence using the method of backward substitutions:

   • M(n) = M(n - 1) + 1
   • Substitute M(n - 1) = M(n - 2) + 1: M(n) = (M(n - 2) + 1) + 1 = M(n - 2) + 2
   • Substitute M(n - 2) = M(n - 3) + 1: M(n) = (M(n - 3) + 1) + 2 = M(n - 3) + 3
   • Continuing this pattern, after i substitutions, we get: M(n) = M(n - i) + i
   • To reach the initial condition M(0) = 0, we set n - i = 0, which means i = n.
   • Substitute i = n into the general pattern: M(n) = M(n - n) + n = M(0) + n
   • Since M(0) = 0: M(n) = 0 + n = n

Thus, the recursive algorithm for computing n! performs n multiplications.

The time complexity of computing n! using the given recursive algorithm is Θ(n), as the number of basic operations (multiplications) grows linearly with the input size n.

Explain the recursive algorithm for the Towers of Hanoi problem.

The Towers of Hanoi is a classic puzzle consisting of n disks of varying sizes and three pegs, which we can label Source, Auxiliary, and Destination. Initially, all disks are stacked on the Source peg in decreasing order of size from bottom to top.

The objective is to move the entire stack to the Destination peg, following two simple rules:

1. Only one disk can be moved at a time.

2. A larger disk can never be placed on top of a smaller one.

The problem has a remarkably elegant recursive solution.

The Recursive Algorithm

To move a stack of n disks from a source peg to a destination peg, we follow these three steps:

1. Recursively move n−1 disks from the Source to the Auxiliary peg. This step uses the Destination peg as a temporary holder.

2. Move the single largest disk (disk n) from the Source to the Destination peg. This is the basic operation.

3. Recursively move the n−1 disks from the Auxiliary to the Destination peg. This time, the Source peg is used as the temporary holder.

The base case for the recursion occurs when we need to move just one disk (n=1), which involves simply moving that disk directly from its source to its destination.

Towers of Hanoi algorithm has a time complexity of Θ(2^n). It is a classic example of an exponential-time algorithm, where the elegant and simple recursive code masks a runtime that grows extremely quickly with the input size n.

Set up the recurrence relation for the number of moves in the Towers of Hanoi problem and solve it to determine the algorithm's time efficiency.

Page 100

The problem has an elegant recursive solution: To move n > 1 disks from a source peg to a destination peg (with an auxiliary peg):

1. Recursively move n - 1 disks from the source peg to the auxiliary peg.
2. Move the largest disk (the nth disk) directly from the source peg to the destination peg. This is considered the basic operation.
3. Recursively move the n - 1 disks from the auxiliary peg to the destination peg. If n = 1, simply move the single disk directly from the source to the destination peg.

Let M(n) denote the number of moves required to solve the Tower of Hanoi puzzle for n disks.

Based on the recursive solution described above, we can set up the recurrence relation:

• For n > 1: To move n disks, we perform M(n-1) moves for the first recursive step, plus 1 move for the largest disk, plus another M(n-1) moves for the second recursive step. Thus, the recurrence equation is: M(n) = M(n - 1) + 1 + M(n - 1). This simplifies to: M(n) = 2M(n - 1) + 1.

• Initial Condition: For the base case of n = 1 disk, only one move is required. So, M(1) = 1.

Solving the Recurrence Relation

We can solve the recurrence M(n) = 2M(n - 1) + 1 with M(1) = 1 using the method of backward substitutions:

1. M(n) = 2M(n - 1) + 1

2. Substitute M(n - 1) = 2M(n - 2) + 1: M(n) = 2[2M(n - 2) + 1] + 1 = 2^2 M(n - 2) + 2 + 1

3. Substitute M(n - 2) = 2M(n - 3) + 1: M(n) = 2^2 [2M(n - 3) + 1] + 2 + 1 = 2^3 M(n - 3) + 2^2 + 2^1 + 2^0

4. Generalizing the pattern after i substitutions: M(n) = 2^i M(n - i) + (2^(i-1) + ... + 2^1 + 2^0) The sum 2^(i-1) + ... + 2^1 + 2^0 is a geometric series sum equal to 2^i - 1. So, M(n) = 2^i M(n - i) + 2^i - 1

5. To reach the initial condition M(1), we set n - i = 1, which means i = n - 1. Substitute i = n - 1 into the formula: M(n) = 2^(n-1) M(n - (n - 1)) + 2^(n-1) - 1M(n) = 2^(n-1) M(1) + 2^(n-1) - 1

6. Substitute the initial condition M(1) = 1: M(n) = 2^(n-1) * 1 + 2^(n-1) - 1M(n) = 2^(n-1) + 2^(n-1) - 1M(n) = 2 * 2^(n-1) - 1M(n) = 2^n - 1.

Time Efficiency

The solution M(n) = 2^n - 1 shows that the number of moves, and thus the time complexity, grows exponentially with the number of disks n.

Therefore, the order of growth of the algorithm's time efficiency for the Towers of Hanoi problem is Θ(2^n). This means it is an exponential algorithm. Even for moderate values of n, the algorithm will run for an unimaginably long time. For example, if monks could move one disk per minute, moving 64 disks would take approximately 3.5 * 10^13 years.

Solve the following recurrence relations to determine their order of growth:

a) Solve T(n) = 2T(n/2) + n, for n > 1, T(1) = 1. (You may assume n is a power of 2).

This recurrence relation is a classic example of a divide-and-conquer recurrence. It follows the general form T(n) = aT(n/b) + f(n), where a is the number of subproblems, n/b is the size of each subproblem, and f(n) is the time spent on dividing the problem and combining solutions.

In this specific recurrence:

• a = 2 (two subproblems)
• b = 2 (each subproblem is half the size of the original)
• f(n) = n (linear time for division and combination)

To solve such recurrences and determine their order of growth, the Master Theorem is a highly convenient and widely used tool.

The Master Theorem states: If T(n) = aT(n/b) + f(n) and f(n) ∈ Θ(n^d) where d ≥ 0, then:

1. T(n) ∈ Θ(n^d) if a < b^d
2. T(n) ∈ Θ(n^d log n) if a = b^d
3. T(n) ∈ Θ(n^(logb a)) if a > b^d

Let's apply it:

• We have f(n) = n. This means f(n) ∈ Θ(n^1), so d = 1.
• Now, compare a with b^d:
  • a = 2
  • b^d = 2^1 = 2
• Since a = b^d (2 = 2), we fall into the second case of the Master Theorem.

Therefore, the order of growth for T(n) is Θ(n^d log n) = Θ(n^1 log n) = Θ(n log n).

We can also solve this using the method of backward substitutions, assuming n = 2^k (so k = log2 n): and T(n) = 2T(n/2) + n

Divide by n: T(n)/n = T(n/2)/(n/2) + 1 Let S(k) = T(2^k) / 2^k.

Then the recurrence becomes S(k) = S(k-1) + 1.

With the initial condition T(1) = 1, for k = 0, n = 2^0 = 1. S(0) = T(1)/1 = 1.

This is a simple arithmetic progression: S(k) = S(0) + k = 1 + k.

Substituting back S(k) = T(n)/n and k = log2 n: T(n)/n = 1 + log2 n

Solution: T(n) = n(1 + log2 n) = n + n log2 n Order of Growth: Θ(n log n).

b) T(n) = 3T(n-1), for n > 1, T(1) = 4.

This recurrence relation is a decrease-by-one recurrence, where the problem size is reduced by a constant amount in each step. It is a linear first-order homogeneous recurrence with constant coefficients.

We can solve this using the method of backward substitutions: T(n) = 3T(n-1) Substitute T(n-1): T(n) = 3 * [3T(n-2)] = 3^2 T(n-2)

Substitute T(n-2): T(n) = 3^2 * [3T(n-3)] = 3^3 T(n-3)

Observing the pattern, after i substitutions, we get: T(n) = 3^i T(n-i)

We need to reach the initial condition T(1) = 4. This happens when n - i = 1, which implies i = n - 1. Substitute i = n - 1 into the pattern: T(n) = 3^(n-1) T(1) Now, substitute the initial condition T(1) = 4: Solution: T(n) = 4 * 3^(n-1)

To determine the order of growth, we look at the dominant term of the solution. The function 3^(n-1) is an exponential function. Exponential functions a^n have different orders of growth for different bases a > 0.

Order of Growth: Θ(3^n).