Exercise VII

Consider the following implementation of countup:

public static void countup(int n) {
  for (int i = 1; i <= n; i++) {
    System.out.println(i);
  }
}

public static void countup(int n) {
  if (n > 1) {
    countup(n - 1);
  } 
  System.out.println(n);
}

Exercise Complete the following table. Use Big-Oh notation to asymptotically describe time/space complexities.

countupTime ComplexitySpace ComplexityInput SpaceAuxiliary Space
First program
Second prog.
Solution
countupTime ComplexitySpace ComplexityInput SpaceAuxiliary Space
First$O(n)$$O(1)$$O(1)$$O(1)$
Second$O(n)$$O(n)$$O(1)$$O(n)$

Each recursive call creates a function activation record (or stack frame) in memory. Each activation record is a memory allocation for the function with space for local variables, etc. Each activation record for the recursive countup requires $O(1)$ space, and there will be $n$ of them, thus $O(n)$ total space.

Resources