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

Resources