Exercise II

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

Consider the following implementations of Arrays.reverse:

public class Arrays { public static <T> void reverse(T[] arr) { T temp; for (int i = 0, j = arr.length - 1; i < j; i++, j--) { temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } }
public class Arrays { public static <T> void reverse(T[] arr) { int n = arr.length; T[] tmp = (T[]) new Object[n]; for (int i = 0; i < n; i++) { tmp[i] = arr[n - i - 1]; } for (int i = 0; i < n; i++) { arr[i] = tmp[i]; } } }

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

Arrays.reverseTime ComplexitySpace ComplexityInput SpaceAuxiliary Space
First program
Second prog.
Solution
Arrays.reversTime ComplexitySpace ComplexityInput SpaceAuxiliary Space
First programO(n)\Omicron(n)O(n)\Omicron(n)O(n)\Omicron(n)O(1)\Omicron(1)
Second prog.O(n)\Omicron(n)O(n)\Omicron(n)O(n)\Omicron(n)O(n)\Omicron(n)