Time Complexity of a for loop

Question

So I'm not really understanding a few things here, when counting the steps in for(int i = 1; i <= n; i++) the answer is:

1 for assignment int i = 1, n+1 for i <= n and n for i++ which comes out to a total of 2n+2. My confusions is in 3 parts:

1.) Isn't the assignment int i = 1; also n? If lets say, n = 5, won't we end up assigning int i = 2, int i = 3... etc?

2.) For i <= n, is it n+1 because you are performing n checks and + 1 when it's false?

3.) Last, is i++ n because you are performing n additions?

Looks like you need to develop some common sense and the ability to read and interpret a beginner Java tutorial. Do you really think that assigning 1 to a variable will assign 2 and 3 to it? — The Paramagnetic Croissant
– The Paramagnetic Croissant, Commented Jan 17, 2015 at 18:13

mrk · Accepted Answer · 2015-01-17 18:12:07Z

For loop looks like for(INIT; CONDITION; INCREMENT) { /* ... */ }. The INIT part executes once only. This is equivalent to:

INIT while(CONDITION) { /* ... */ INCREMENT }

Eran · Accepted Answer · 2015-01-17 18:10:29Z

The initialization int i=1; is performed only one time at the beginning of the loop, regardless of n.

As for 2) and 3), you are correct.

2 Answers 2