-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$
6
  • 3
    $\begingroup$ There are so many questions about runtime of for loops around, have you looked at any of them? $\endgroup$
    – Raphael
    Mar 8, 2013 at 20:45
  • 3
    $\begingroup$ Ultimately, it depends also on what happens inside the loop. $\endgroup$ Mar 8, 2013 at 20:50
  • $\begingroup$ @DaveClarke Assuming inside the loop everything is O(1) $\endgroup$ Mar 10, 2013 at 16:06
  • $\begingroup$ @Raphael Yes, I searched, but couldn't find anything related well enough to my problem $\endgroup$ Mar 10, 2013 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, 2013 at 18:26

1 Answer 1

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$
1
  • $\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$ Mar 10, 2013 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.