Size of the Input

  • Describe the runtime as a function of the input size.

Consider the following program:

public class Arrays {
  public static <T> void print(T[] arr) {
    for (int i = 0; i < arr.length; i++) {
      System.out.println(arr[i]);
    }
  }
}

To determine the runtime of Arrays.print, we need to know the size of the input array (arr).

The runtime here, as in many cases, is a function of the input size.

Exercise Count the number of steps Arrays.print takes to execute. Write the count as a function T(N)T(N) where NN is the size of the input array.

Solution 
public class Arrays {
  public static <T> void print(T[] arr) {
    for (int i = 0; i < arr.length; i++) { // 1 + N+1 + N
      System.out.println(arr[i]);          // 1 * N
    }
  }
}

T(N)=3N+2 T(N) = 3N + 2

We assumed memory access is "free" under the RAM model (i.e., arr.length and arr[i] are free operations).