Analyzing Recursive Code

Analyze each of the algorithm listings below. Before you dive in and start doing math, take a moment to read the code carefully and develop a prediction for the result that you expect. Will the run-time be linear? quadratic? exponential? something else? Write down your big-\(\Theta\) prediction, then check it by doing a detailed analysis.

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