Lab 8: Recursion and Big-O revisited

Creating the necessary folder

Make sure to create a subfolder called lab8 within your cs112 folder, and put all of the files for this lab in that folder.

Task 1: Practice algorithm analysis

Consider the following code fragment:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < 2*n; j++) {
        methodA();

        for (int k = 0; k < n + 1; k++) {
            methodB();
        }
    }

    for (int j = 0; j < i; j++) {
        methodC();
    }

    if (i % 2 == 0) {
        methodD();
    }
}

For each of the following, find the function that expresses the number of times each part of the code is executed for a given value of n, and then determine the corresponding big-O expression.

1. the number of times methodA() is called
2. the number of times methodB() is called
3. the number of times methodC() is called
4. the number of times methodD() is called

Consider the following code fracgment:

public static int mystery(int a[]) {
    int n = a.length;
    int result = 0;

    for (int i = 1; i < n; i++) {
        int x = a[i];        // Question 2

        int sum = 0;
        for (int j = 0; j < 3; j++) {
            sum *= a[i];     // Question 3
        }
        result += sum;

        int j = i;
        while (j > 0) {
            result += a[j];   // Question 4
            j--;
        }
    }

    return result;
}

a) What is the big-O expression for the number of times that the line

int x = a[i];

is executed? ___

b) What is the big-O expression for the number of times that the line

sum *= a[i];

is executed? ___

c) What is the big-O expression for the number of times that the line

result += a[j];

is executed? ___

Task 2: Tracing a recursive method

Consider the following method:

public static int test(int a, int b) {
   if (a < b) {
      return 0;
   } else {
      return 1 + test(a-b, b);
   }
}

What is returned by the call test(15, 4)?

How many times is the method called during the execution of test(15, 4) – including the initial call?

Task 3: Recursion and Arrays

Write a recursive method named reverseArray that reverses the elements of an array. Example, given the following array declaration:

int[] arr = {1,2,3,4,5,6,7,8}

After the reverseArray method is called, the println statement

System.out.println(Arrays.toString(arr)) would output:

results in the following output:

[8,7,6,5,4,3,2,1]

Last updated on March 19, 2026.