educative.io

Challenge 7 Nested Loop with Multiplication (Pro)

Courses
,
#1

Challenge 7 Nested Loop with Multiplication (Pro)

Why is the number of executions of line 9 while (j < i) is log_2(n) ?
Shouldn’t it be n ?

In the solution for Java, the number of executions of while (j < i) is n.

I don’t understand how it is calculated and why it’s different for JS and Java.

Could you please explain how it is calculated?

Course: https://www.educative.io/collection/5642554087309312/5663204961157120
Lesson: https://www.educative.io/collection/page/5642554087309312/5663204961157120/5650387168133120

#2

Hi @Iryna_D,
As mentioned above the time complexity table:
“Note that j is not reset to 1 in the code since the j is immediately doubled, therefore inner while loop will run O(log_2(n)) times for all the iterations of the outer loop.”

In the solution for java, the number of execution of while(j < i) is also O(log_2(n)). The time complexity of the whole code solution is O(n). The time complexities for Java and JavaScript are not different for this challenge.
For reference, you can look at this lesson.

We hope Educative has inspired you to further your learning, and please drop us a note if you have any other questions or concerns.
Happy learning!

#4

Hi @Kanwal_Saeed , I meant the while(j < var) condition, not the code inside the while loop.
The number of executions of the condition while(j < var) is log_2(n) in the JavaScript solution.
Why is it simply log_2(n) , not log_2(n) + 1 like in other challenges with while loops (e.g challenge 6)?

#5

The number of times this condition will execute depends on the value of j. If you look closely, you will notice that in challenge 6, line 7, we are resetting the value of j to 1, whereas in this solution, the value of j remains the same. So, the time complexity will vary according to the number of times the code is executed i.e…, the condition is satisfied, which will depend on the value of j. That’s why the time complexity varies.

#6

Kanwal_Saeed, But isn’t the condition supposed to run more times than the loop body?
In all other challenges, the condition complexity = loop body complexity + 1.