$ $

Recurrences

Counting Activation Records

Counting Operations

Analyzing Recursive Algorithms: Stage 1

Warm-up Exercise

Develop a recurrence that describes the number of multiplication operations performed by the following code block:

public static int fun(int n) {
    if (n == 1) {
        return 5;
    } else {
        int sum = 1;
        for (int i = 0; i < 7; i++) {
            sum *= 2;
        }
        return sum * fun(n - 1);
    }
}

\(T(??) = ??\)

\(T(n) = ??\)

Warm-up Exercise

public static int fun(int n) {
    if (n == 1) {
        return 5;
    } else {
        int sum = 1;
        for (int i = 0; i < 7; i++) {
            sum *= 2; // Seven here.
        }
        return sum * fun(n - 1); // One here.
    }
}

\(T(1) = \color{orange}{0}\)

\(T(n) = \color{red}{8} + \color{green}{T(n-1)}\)

Another Exercise

Write a recurrence relation that describes the number of additions performed by this method.

   public static int fun1(int n) {
        if (n == 0) {
            return 20;
        } else {
            
            int result = 2 * n;

            return result - (fun1(n - 1) + fun1(n - 1));
        }
    }

One More…

Write a recurrence relation that describes the number of assignments to sum performed by this method.

    public static int fun(int n) {

        if (n <= 1) {
            return 8;
        }

        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += fun(n - 1) + fun(n - 2);
        }
        return sum;
    }

One More…

Write a recurrence relation that describes the number of assignments to sum performed by this method.

    public static int fun(int n) {

        if (n <= 1) {
            return 8;
        }

        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += fun(n - 1) + fun(n - 2);
        }
        return sum;
    }

We need two initial conditions!

\(T(0) = 0\)

\(T(1) = 0\)

\(T(n) = n + 1 + nT(n-1) + nT(n-2)\)

Part 2: Solving the Recurrence

Next time…