-2
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ There are so many questions about runtime of for loops around, have you looked at any of them? $\endgroup$ – Raphael Mar 8 '13 at 20:45
  • 3
    $\begingroup$ Ultimately, it depends also on what happens inside the loop. $\endgroup$ – Dave Clarke Mar 8 '13 at 20:50
  • $\begingroup$ @DaveClarke Assuming inside the loop everything is O(1) $\endgroup$ – CodyBugstein Mar 10 '13 at 16:06
  • $\begingroup$ @Raphael Yes, I searched, but couldn't find anything related well enough to my problem $\endgroup$ – CodyBugstein Mar 10 '13 at 16:08
  • $\begingroup$ @Imray Have a look at my answer to this question. Form a summation expression, and solve it. For asymptotic complexities ($O$, $\Theta$), you can find many methods in the reference questions under the "Asymptotics" heading. $\endgroup$ – Paresh Mar 10 '13 at 18:26
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How do I format latex equations to avoid inserting \quad spaces ? Without, equations and subsequent characters appear correctly in the preview, but not in the saved answer! $\endgroup$ – Massimo Cafaro Mar 10 '13 at 18:01

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.