Recurrence Lab

Introduction

Your goal in this lab is to gain more experience solving recurrences.

Exercise 1

Develop a recurrence and use the method of backward substitution to determine the number of multiplication operations that will be performed by the following method.

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

Exercise 2

Develop a recurrence and use the method of backward substitution to determine the number of array accesses performed by the following function.

FUNCTION fun4(numbers: array)
    RETURN fun4helper(numbers, numbers.length - 1)
    
FUNCTION fun4helper(numbers: array, index: integer)
    IF index = 0
        RETURN numbers[index]
        
    sum := 0
    
    FOR i =  0 to index
        sum := sum + numbers[index]
        
    RETURN sum + fun4helper(numbers, index - 1)

Exercise 3

Develop a recurrence and use the method of backward substitution to determine the number times the body of the inner loop is executed in the following method. (For the purpose of analysis, you may assume that the length of numbers is a power of 2)

public static int fun3(int[] numbers) {
    return fun3(numbers, numbers.length);
}

private static int fun3(int[] numbers, int index) {
    if (index <= 1) {
        return 3;
    }

    for (int i = 0; i < 4; i++) {
        fun3(numbers, index / 2);
    }

    int sum = 0;
    for (int i = 0; i < index; i++) {
        for (int j = 0; j < index; j++) {
            sum += numbers[i] + numbers[j]; //count this
        }
    }
    return sum;
}

Lab Submission

If you are in class today, there is nothing to submit. If you were absent, you must submit your work to Canvas by the due date.