How to count primitive comparison operations of for loop when initialization is non-zero?

Question

For a for loop as follows:

for(i = 0; i < n; i++){

}

The initialization counts for 1 operation, the conditional test executes n + 1 times and the increment n times. This gives a T(n) = 1 + n + 1 + n = 2n + 2. This I understand. Where I get confused is when i is assigned a non-zero value. I assume when i = 1 then the comparison only occurs n times and results in T(n) = 1 + n + n = 2n + 1? But then what happens if i is assigned 10? Or a negative value? Are the number of comparisons still n or n + 1?

Answer 1

Let us replace the initialization by 0 with an initialisation by i0 to make the whole thing more general.

So the pseudo code looks like this:

i0 = 0;
for (i = i0; i < n;  i++) { }

Now we can state the formula more general:

T(n) = T_init(n) + T_cmp(n) + T_inc(n)
     = 1         + (n-i0+1) + (n - i0)
     = 2*(n - i0 + 1)
     = 2*n - 2*i0 + 2

T_init should be clear. As you said initialisation is always run only once, independent of n.

The comparison is always run directly after the increment but also once before the first loop iteration. So T_cmp(n) = T_inc(n) + 1.

You could also try it with some helper functions:

function init() {
  print("init");
  return i0;
}
function cmp(i,n) {
  print("cmp");
  return i < n;
}
function inc(i) {
  print("inc");
  return i+1;
}
for (i = init(); cmp(i,n); i = inc(i)) { }

This should print a line for each operation so you can count lines to measure "time". (Well it is pseudo code so you have to adopt to your language to run it :)