Choosing the Input

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

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

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
}