educative.io

Educative

Run times of Comparison statement - Simple for loop

According to the text in the “Simple for-loop” section:
“This means the loop increment statement runs a total of n times. The comparison statement also runs n times. The initialization runs once. Summing them up, we get a running time complexity of the for loop of n+n+1+1=2n+2.”

I am confused. Is it a typo in the comparison statement? Comparison statement should runs n+1 times(?)

Thank you.

Hi @cyh_ho

Thanks for taking out your time to report this. We have updated the lesson along with an added explanation to Why the comparison statement runs n+1 times?

Hope you’re having fun while learning with Educative!

Regards,
Team Educative

for (int i = 0; i < n; i++) {
for (int x = 0; x < m; x++) {
// Statement(s) that take(s) constant time
}
}

I am confused with my result vs what the material has …
outer loop i get : 3n+2 breakdown : (1 + (n+1) + 2n)
inner loop i get : n+m+2nm+1
statements : cnm

am i doing something wrong ?

Hi @rohith,

This is Fatimah Abdullah from Educative. Thank you for reaching out to us!

In response to your question, let’s look at each point one by one.

It seems that you are doing a mistake in calculating how many times i++ should run. This statement only runs n times, not 2n. The reason is that the condition says that i < n, so it can only increase n times. Increasing 2n times is not possible. So, the total complexity of the outer loop will be 2n + 2.

First, when we calculate the complexity of the inner loop by itself, it will be 2m + 2. Now, as we already know that each statement inside the outer loop runs n times, so as the inner loop is also inside the outer loop, it would also run n times. Thus, the total complexity of the inner loop is n x (2m + 2) = 2nm + 2n.

I hope this clears up your confusion. If you have any further queries, please let us know.

Best Regards,

Fatimah Abdullah | Developer Advocate
Educative

1 Like

In example 1. It said that i++ consists of two steps: addition and assignment. Therefore, it takes 2n. However, it did differently in Common Complexity Scenarios.
I am confused about the time complexity of x++ and +=. Beat me!

Hi @Bo_Su,

This is Fatimah Abdullah from Educative. Thank you for reaching out to us!

In response to your question, Yes, I understand why this might be confusing for you. It is true that previously the increment x++ was mentioned to have broken been down into 2 operations. However, in this lesson, it is considered that increment only takes 1 unit time. The reason is that considering as we are performing asymptotic analysis, it does not make any difference in the Big-Oh terms. It is not a necessary convention to break down the increment into 2 units, it is just a preference. You will observe that in much beginner-level literature, it may be broken. But, as the topic gets advanced and we start considering the asymptotic analysis then in most cases, you will observe that it is only considered 1 unit .

I hope this answers your question. However, feel free to reach out if you have any follow-up questions.

Best Regards,

Fatimah Abdullah | Developer Advocate
Educative

1 Like