Complexity of slightly tricky for loop

Question

I'm trying to determine the complexity of this for loop:

for (int j =3; j <= n-2; j+=2) {
   ....
}

By trying out lots of examples, I came up with $\frac{n-4}{2} + 1$. This seems to work with every number now.

However, I am looking for a systematic and quick way to find these sorts of complexities. For example, can you show me the proper way to find the complexity for the above loop?

Answer 1

There is no systematic way, since the expressions in the loop may be arbitrary. For your particular case, assuming that the statements executed are $O(1)$, then the complexity is obviously $O(n)$. If you instead want to determine the exact number of iterations, you may reason as follow. As noted by @blob, you are counting odd numbers starting from 3.

The number of iterations depend on the parity of $n$, i.e., you must consider two cases: $n$ is even or odd. Another thing you must take into account is that the loop is executed one more time simply to test the termination condition, without executing the loop statements.Since you are executing this last iteration without counting the corresponding odd number, you may consider that, equivalently, you are including 1 (which is excluded since you start from 3).

Let $n = 2k, k\in N\quad$. In this case, the total number number of iterations is $(n-2)/2 \quad$ including the last one that simply terminates the loop without executing the loop statements. Now, since $n$ is even, from $n = 2k \quad$ you can immediately derive that the total number of iterations is also given, equivalently, by $k - 1$.

Let $n = 2k + 1, k\in N \quad$. Reasoning as before, let $x = n + 1 \quad$, which is the even successor of $n$. Since $x = 2k + 2 = 2 * (k+1) \quad$, you can conclude immediately that the total number of iterations is given by $k + 1 - 1 = k \quad$ when $n$ is odd.

Then, you may simply say that the total number of iterations is simply $\lceil n/2 \rceil - 1\:$ or $\lceil (n - 2)/2 \rceil \quad$, without taking into account the parity of $n$. Note that this is equivalent to your own answer $\lceil (n - 4)/2 \rceil + 1\:$.

Example: for $n = 10 = 2 * 5 \quad$, the iterations are 5 - 1 = 4. For $n = 9 = 2 * 4 + 1 \quad$, the iterations are 4.