CODEWITHSUNDEEP
javaalgorithmdata-structuresbig-otime-complexity
Sierra Bravo
Sierra Bravo

Reputation: 41

Time Complexity of a for loop

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?

Upvotes: 0

Views: 828

Answers (2)

mrk
mrk

Reputation: 3191

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

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

Upvotes: 2

Eran
Eran

Reputation: 393821

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.

Upvotes: 1

Related Questions