# Application of floors and ceilings to the time complexity of loop with constant index increment

Consider the number of times that 'statement' runs in the following examples. I am confused as to the applications of floors and ceilings when calculating the loop complexity.

for (int i = 1; i < m; i += a) {
statement;
}


In this example, I count the loop by establishing a bijection between the loop iteration and the values of i that do not break the termination condition, values identified by sequence 1, 1 + a, 1 + 2a, ..., 1 + (n-1)a.

Solving for the termination condition:

1 + (n-1)a = m => n - 1 = (m - 1)/a, since the only the first n - 1 terms in the sequence are counting the number of iterations.

The number of iterations being an integer becomes floor((m-1)/a), in my understanding. However, in many solutions I see that the number of iterations is just m/a -- the discussion on floors and ceilings is neglected.

How do I get from the ceiling notation to the much simpler looking m/a figure?

You are technically right, and if you want an exact value of the number of loop iterations, you can't forget the floor.

However, when doing asymptotical time complexity analysis, you can often toss terms that are negligible in front of other terms. In this case, $$\frac{m}{a} - \left\lfloor\frac{m-1}{a}\right\rfloor \leq 1+\frac{1}{a}$$ which is negligible in front of $$\frac{m}{a}$$ (for $$m$$ big enough).

See here for more details.