Nonrecursive & Recursive Algorithm Analysis

Mathematical Analysis of Nonrecursive and Recursive Algorithms

Levitin presents a standardized, step-by-step mathematical methodology for determining the exact operation counts of algorithms.

---

1. Analysis of Nonrecursive Algorithms

General Plan for Nonrecursive Algorithms

1. Decide on parameter $n$ indicating input size.
2. Identify the algorithm’s basic operation (usually located in the innermost loop).
3. Check whether operation count depends on input properties beyond $n$. If it does, analyze best-case, worst-case, and average-case separately.
4. Set up a summation expressing the number of times the basic operation is executed.
5. Simplify the sum using standard summation formulas and rules.

Standard Summation Formulas

$$\sum_{i=l}^u 1 = u - l + 1$$ $$\sum_{i=1}^n i = 1 + 2 + \dots + n = \frac{n(n+1)}{2} \approx \frac{1}{2} n^2 \in \Theta(n^2)$$ $$\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} \approx \frac{1}{3} n^3 \in \Theta(n^3)$$ $$\sum_{i=0}^n a^i = \frac{a^{n+1} - 1}{a - 1} \quad (a \ne 1)$$

Nonrecursive Example: Maximum Element

MaxElement(A[0..n-1]):
    maxval = A[0]
    for i = 1 to n - 1 do:
        if A[i] > maxval then:
            maxval = A[i]
    return maxval

• Basic operation: Comparison A[i] > maxval.
• Summation:

$$C(n) = \sum_{i=1}^{n-1} 1 = (n - 1) - 1 + 1 = n - 1 = \Theta(n)$$

Nonrecursive Example: Matrix Multiplication

Multiplying two $n \times n$ matrices $C = A \times B$:

MatrixMultiplication(A, B):
    for i = 0 to n - 1 do:
        for j = 0 to n - 1 do:
            C[i, j] = 0.0
            for k = 0 to n - 1 do:
                C[i, j] = C[i, j] + A[i, k] * B[k, j]

• Basic operation: Multiplication A[i, k] * B[k, j].
• Summation:

$$M(n) = \sum_{i=0}^{n-1} \sum_{j=0}^{n-1} \sum_{k=0}^{n-1} 1 = \sum_{i=0}^{n-1} \sum_{j=0}^{n-1} n = \sum_{i=0}^{n-1} n^2 = n^3 = \Theta(n^3)$$

---

2. Analysis of Recursive Algorithms

General Plan for Recursive Algorithms

1. Decide on parameter $n$ indicating input size.
2. Identify basic operation.
3. Check whether operation count depends on input properties beyond $n$.
4. Set up a recurrence relation with an appropriate base condition (initial condition) expressing the count of basic operations.
5. Solve the recurrence using backward substitution or known formulas (such as the Master Theorem).

Method of Backward Substitution

Backward substitution works by repeatedly expanding the recurrence using its own definition until a pattern emerges, expressing $T(n)$ in terms of the initial condition.

Example: Recursive Factorial

Factorial(n):
    if n == 0 return 1
    else return Factorial(n - 1) * n

Recurrence:

$$M(n) = M(n-1) + 1 \quad \text{for } n > 0, \quad M(0) = 0$$

Applying backward substitution:

$$\begin{aligned} M(n) &= M(n-1) + 1 \\ &= [M(n-2) + 1] + 1 = M(n-2) + 2 \\ &= [M(n-3) + 1] + 2 = M(n-3) + 3 \\ &\ \ \vdots \\ &= M(n-k) + k \end{aligned}$$

The base case is reached when $n - k = 0 \implies k = n$:

$$M(n) = M(0) + n = 0 + n = n = \Theta(n)$$

---

Exercises

Exercise 1

Analyze the number of multiplications made by the recursive algorithm that computes $2^n$ by doubling:

$$P(n) = \begin{cases} 1 & \text{if } n = 0 \\ 2 \cdot P(n-1) & \text{if } n > 0 \end{cases}$$

Set up the recurrence and solve it by backward substitution.

Show solution ↓Hide solution ↑

Solution

Let $M(n)$ be the number of multiplications:

• Base case: $M(0) = 0$.
• Recurrence: $M(n) = M(n-1) + 1$ for $n > 0$.

Backward substitution:

$$\begin{aligned} M(n) &= M(n-1) + 1 \\ &= M(n-2) + 2 \\ &= \dots = M(n-i) + i \end{aligned}$$

At $i = n$: $M(n) = M(0) + n = n$. Therefore, the algorithm performs exactly $n$ multiplications, which is $\Theta(n)$.

Exercise 2

Evaluate the following nested summation:

$$S(n) = \sum_{i=1}^n \sum_{j=1}^i (i + j)$$

Show solution ↓Hide solution ↑

Solution

Split the inner summation:

$$\sum_{j=1}^i (i + j) = \sum_{j=1}^i i + \sum_{j=1}^i j = i \cdot i + \frac{i(i+1)}{2} = i^2 + \frac{i^2 + i}{2} = \frac{3i^2 + i}{2}$$

Now compute the outer summation:

$$S(n) = \sum_{i=1}^n \frac{3i^2 + i}{2} = \frac{3}{2} \sum_{i=1}^n i^2 + \frac{1}{2} \sum_{i=1}^n i$$

Substitute standard formulas:

$$S(n) = \frac{3}{2} \left[\frac{n(n+1)(2n+1)}{6}\right] + \frac{1}{2} \left[\frac{n(n+1)}{2}\right]$$$$= \frac{n(n+1)(2n+1)}{4} + \frac{n(n+1)}{4} = \frac{n(n+1)(2n+2)}{4} = \frac{n(n+1)^2}{2} = \Theta(n^3)$$