Choosing the Input

Expressing the runtime as a function of the size of the input allows us to analyze how performance scales with increasing input size.

In the previous example, it was the size of the input array. In the following example, it is the value of the variable num:

public int myStrangeSum (int num) {
  int sum = 0;
  int count = 2 * num;
  for (int i = 0; i < count; i += 4) {
      sum += i;
  }
  return sum;
}

Exercise Count the number of steps myStrangeSum takes to execute. Write the count as a function $T(N)$ where $N$ is the value of variable num.

public int myStrangeSum (int num) {
  int sum = 0;                            // 1
  int count = 2 * num;                    // 2
  for (int i = 0; i < count; i += 4) {    // 1 + (N/2 + 1) + N/2
      sum += i;                           // 1 * N/2
  }
  return sum;                             // 1
}