Exercise I

  • Express the space requirements for a given code segment as a function of the input size in the worst-case scenario.

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$\Omicron(n)$$\Omicron(1)$$\Omicron(1)$$\Omicron(1)$
Second$\Omicron(n)$$\Omicron(n)$$\Omicron(1)$$\Omicron(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 $\Omicron(1)$ space, and there will be $n$ of them, thus $\Omicron(n)$ total space.

Resources