1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.