Simple loops complexity analysis

[lost110]

for (int i = k; i < n; i = i + m)
{
statement1;
statement2;
}

From the above loop, there are three facts taken! I have understood the first one. But Can't understand the rest of 3. Can anyone explain those? I think that "/" here means "OR" .Thanks! Here are those:
1)The initialization statement, i = k, is executed one time.

2)The condition, i < n, is executed (n – k) / m + 1 times.

3)The update statement, i = i + m, is executed (n – k) / m times.

4)Each of statement1 and statement2 is executed (n – k) / m times.

[MikeyBoy]

I think that "/" here means "OR"

I think you're wrong. I think "/" here means what it usually means in algebraic expressions.

This is all about working out how many times the loop will iterate.

You need to figure out:

a) What is the range of values of i over which the loop will iterate
b) By how much is i incremented on each iteration

Once you've understood that, it should be clear how to combine those two to calculate the number of iterations.

Do you understand why the answer to (2) is 1 higher than the answers to (3) and (4) ?

[lost110]

I am gonna run it with starting values
m= 1
n = 10
k=5
With this (i < n) should be executed 6 times(after the 5th iteration, i < n condtion will still be checked) ...so that means that (i<n) should run : k+1 times.

But yes! The increment and in loop statement are making sense. 10-5/1 = 5 ...they both should run 5 times. .....but not getting the i<n statement!

[Handy Andy]

Hello lost110,

Give this a run and see what you get:

#include <iostream>
#include <iomanip>
#include <string>
#include <limits>

int main()
{
    int k{ 5 }, n{ 10 }, m{ 1 };

    for (int i = k; i < n; i = i + m)
    {
        std::cout << "\n i = " << i << '\n';
        
        std::cout << " n = " << n << '\n';
    }


	// The next line may not be needed. If you have to press enter to see the prompt it is not needed.
	//std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');  // <--- Requires header file <limits>.
	std::cout << "\n\n Press Enter to continue: ";
	std::cin.get();

	return 0;  // <--- Not required, but makes a good break point.
}

Andy

[lost110]

Andy yes! The inside loop statements are executing 5 times. Which is fine. But I am talking about the i< n statement. My professor says that "condition check" statement executes 1 extra time. So that must be (n-k+1) times.

[lost110]

after the 5th itereation, the condition will still be checked, not executed, but checked!

[seeplus]

Try this:

include <iostream>
#include <iomanip>
#include <string>
#include <limits>

int main()
{
	int k {5}, n {10}, m {1};

	int cond = 0;

	for (int i = k; (std::cout << "cond :" << ++cond << '\n') && i < n; i = i + m)
	{
		std::cout << "\n i = " << i << '\n';

		std::cout << " n = " << n << '\n';
	}
}

This shows the number of times the condition is executed.

[MikeyBoy]

after the 5th itereation, the condition will still be checked, not executed, but checked!

Exactly. The condition needs to be checked one more time, so that the program can decide whether to keep iterating or not.

[Handy Andy]

Hello lost110,

I would say that your professor is correct.

In all my years of working with for loops I have never thought about how mane times the condition is checked, but more concerned about how many times it is "true".

I think I have just accepted that the last time the condition is check and becomes "false" I do not think about counting that time.

I see your point and I think that (n - k + 1) should be correct.

Although it works one change I would consider is i += m. This changes the value of "i"

Andy

[lost110]

I have got it guys! @Andy @Mikeboy@seeplus Thanks a lot