1
$\begingroup$

Consider the following code snippet:

for(int i=0;i<n;i++)

The question I have is: whether this loop is executed $n$ times or $(n+1)$ times?

According to what I understand: when $i=n$, the for loop would increment $i$ to $n+1$ and check if $i<n$ which would evaluate to false and the loop will be exited.

So the increment would be performed a total of $(n+1)$ times. Is this correct? Should we count $(n+1)$ as the number of increment operations performed during algorithm analysis?

I know this would not make any difference to the complexity since $O(n+1) = O(n)$, linear time. But I was just curious to know if my understanding is correct or not.

$\endgroup$
0

2 Answers 2

4
$\begingroup$

Consider the following code snippet:

for(int i=0;i<n;i++)

The question I have is: whether this loop is executed $n$ times or $(n+1)$ times?

This loop executes $n$ times, not $n+1$ times. The first iteration of the loop has $i = 0$; the second has $i = 1$, and so on, up to the last iteration of the loop $i = (n-1)$. Then let us see what happens after that:

  • We get to the bottom of the loop when $i = (n-1)$.

  • At this point, we jump up to the top and execute i++. So now $i = n$.

  • Next, we check the loop condition. We see that i < n is false, so the loop condition is false. That means we exit the loop.

So in total, we executed the loop for $i = 0$, $i = 1$, $i = 2$, up to $i = n-1$. That is in total $n$ times.

Your misconception was that the loop is terminated once $i$ gets to $n + 1$; but actually it is terminated when $i = n$, because $n$ is already not less than $n$.

I know this would not make any difference to the complexity since $O(n+1)=O(n)$, linear time.

That is correct!

$\endgroup$
3
  • 1
    $\begingroup$ Yes! I understand it now!! What was confusing me was whether to count the $i<n$ condition in the number of times for condition is run. Like counting how many times the for statement is executed - count the number of times the code inside the for loop is run (which is n times) + 1 (the time the check i<n fails) $\endgroup$ Feb 28, 2020 at 8:41
  • 1
    $\begingroup$ @JANVI I see, that makes sense! $\endgroup$ Feb 28, 2020 at 15:49
  • 1
    $\begingroup$ @JANVISHARMA, it depends on what you are counting... if you count how many times the i < n is evaluated, it is n +1 times. So you do have a point. $\endgroup$
    – vonbrand
    Mar 3, 2020 at 2:42
1
$\begingroup$

A for loop contains a header specifying the iteration and body that executed once per iteration. What you consider is the header. You must run at least the assignment and comparison once to decide to enter the loop or not. A clever compiler can skip a loop if it is not entering if the values are available on the compile time.

In general, we consider how many times the body is run when we look at the Big-Oh notation. We expect that the most time-consuming part of the loop is the body. As you noted, it will be in the same complexity class. The operations are the assignment $1$, increment $n$ and check run $n+1$ times;

$$Assign \to [Check \to Run body \to Increment]^* \to Check \to Exit$$ i.e. The for loop body run $n$ times, check runs $n+1$ times.

For exact timing, you need more than that. See Knuth's first volume where he calculated it exactly. Also, see Corman et al., they made a similar calculation for the loop.

$\endgroup$
7
  • $\begingroup$ You didn't seem to answer the question, which is whether the loop executes $n$ or $n + 1$ times. I don't think you understood it exactly. $\endgroup$ Feb 26, 2020 at 19:58
  • 1
    $\begingroup$ @6005 Actually it is there. Runbody is one less than the check! $\endgroup$
    – kelalaka
    Feb 26, 2020 at 20:03
  • $\begingroup$ Well now you have added it :) But the rest of the answer seems not relevant to the question $\endgroup$ Feb 26, 2020 at 21:09
  • $\begingroup$ I also think you misunderstood that the question was about the check being run $n + 1$ times. Actually the OP does not talk about the check. The misconception is that $i$ is incremented to $n+1$, when in reality the largest that $i$ gets is $n$. $\endgroup$ Feb 26, 2020 at 21:10
  • 1
    $\begingroup$ Beyond being irrelevant they also raise a lot more questions than they answer, such as, "so if a compiler skips a loop does that mean we should not count it as being executed?" And your use of the kleene star * without explaining what it is is bound to make the reader completely lost (on the small chance they were not lost already). $\endgroup$ Feb 26, 2020 at 21:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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