Analyzing Recursive Algorithms

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;
}