Section 16

Efficient recursion

The Fibonacci sequence is a well-known infinite series in which each number in the series is the sum of the two previous numbers. The complete definition of the sequence is as follows:

F₀ = 0
F₁ = 1
F_n = F_{n - 1} + F_{n - 2}

Given a positive integer n, the method below computes the value of the nth Fibonacci number.

public static int fib(int n) {
    if (n < 0)
        throw new IllegalArgumentException("invalid Fibonacci index");

    if (n == 0)
        return 0;

    if (n == 1)
        return 1;

    return fib(n - 1) + fib(n - 2);
}

1. Draw a tree digram that shows the calls arising from an initial call to fib(4). How many times did we call fib to find the fourth Fibonacci number?

2. Write an iterative version of fib that is more efficient than the recursive version. Challenge: write a more efficient recursive version of fib that only calls fib once for a given parameter. ¹

Asymptotic notation

Recall from lecture that asymptotic notation is a way to compare two mathematical functions by how quickly they grow as their inputs grow in size. There are several different methods of comparison, but the most commonly used method is big O notation. The formal definition follows:

We say “f(x) = O(g(x))” if and only if f(x) is at most c·g(x), for some constant c, as x tends to infinity.

It may help to imagine O() as a function, the big O function, that takes a function and returns an infinite set of member functions that all belong to the same growth class (e.g., exponential, quadratic, logarithmic, et cetera). In this scenario, it would be more appropriate to say that the function f(x) = 2x is in O(x), or f(x) ∈ O(x).

3. Create a chain of inequalities for the following basic big O functions representing classes of asymptotic growth (where c is a constant): O(n), O(1), O(cⁿ), O(n log n), O(log n), O(n^k). Order them from least-fastest growing to fastest growing. ²

For each of the following code fragments, derive a function f(n) that expresses the number of iterations the innermost loop body will run for a given value of n. Then determine which growth class each function is a member of.

4. A simple loop: ³

   for (int i = 0; i < n; i++) {
       System.out.print("*");
   }
   System.out.println();
   

5. Simple nested loops: ⁴

   for (int i = 0; i < n; i++) {
       for (int j = 0; j < n; j++) {
           System.out.print("*");
       }
   }
   System.out.println();
   

6. Triply nested loops: ⁵

   for (int i = 0; i < n; i++) {
       for (int j = 0; j < n; j++) {
           for (int k = 0; k < n; k++) {
               System.out.print("*");
           }
       }
   }
   System.out.println();
   

7. Doubly nested loops, where the innermost loop’s number of iterations is constant: ⁶

   for (int i = 0; i < n; i++) {
       for (int j = 0; j < 3; j++) {
           System.out.print("*");
       }
   }
   System.out.println();
   

8. Doubly nested loops, where the innermost loop’s number of iterations is dependent on the outer loop’s index variable: ⁷

   for (int i = 0; i < n; i++) {
       for (int j = 0; j < i; j++) {
           System.out.print("*");
       }
   }
   System.out.println();
   

Sorting algorithms

For the following sorting algorithms, fill in each step of the algorithm’s execution. Assume that the method swap(arr, i, j) correctly swaps the elements at position i and j in the array arr and returns nothing.

9. Find the code for selection sort below:

   private static int indexSmallest(int[] arr, int lower, int upper) {
       int indexMin = lower;
       for (int i = lower+1; i <= upper; i++){
           if (arr[i] < arr[indexMin])
               indexMin = i;
       }
       return indexMin;
   }
   
   public static void selectionSort(int[] arr) {
       for (int i = 0; i < arr.length - 1; i++) {
           int j = indexSmallest(arr, i, arr.length - 1);
           swap(arr, i, j);
       }
   }
   

   We will trace the action of this algorithm on the following array:

   7

   39

   20

   11

   16

   5

   Trace the algorithm again, this time running on the following input array:

   10

   22

   2

   9

   2

   23

   Show the array after every call to the swap method. Then determine selection sort’s best and worst case time complexity using big O notation, letting the input size (here, arr.length) be n. ⁸

10. Find the code for insertion sort below:

    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i-1]) {
                int toInsert = arr[i];
    
                int j = i;
                do {
                    arr[j] = arr[j-1];
                    j = j - 1;
    
                } while (j > 0 && toInsert < arr[j-1]);
    
                arr[j] = toInsert;
            }
        }
    }
    

    We will trace the action of this algorithm on the following array:

    7

    39

    20

    11

    16

    5

    Trace the algorithm again, this time running on the following input array:

    10

    22

    2

    9

    2

    23

    Show the array after every iteration of the outer loop, if the iteration results in any moves. Then determine insertion sort’s best and worst case time complexity using big O notation, letting the input size (here, arr.length) be n. ⁹

Last updated on July 21, 2025.