educative.io

Educative

Initialisation of counter variable in inner loop

Hello!
I wanted to know if the var j = 0 step is performed for each iteration of the outer loop? Because if that does not happen, then the inner loop executes only n(2m + 1 + cm) times and the var j = 0 shall be counted as a separate instruction and final answer would be: nm(3 + c) = 3n + 3

Hi @Humaira_Fasih !!
In the provided code, the variable j is initialized to 0 before the inner loop. However, the variable j is overwritten in the inner loop declaration as var=0. This indicates that the variable j is re-initialized to 0 for each iteration of the outer loop.

Therefore, the inner loop executes m times for each iteration of the outer loop, resulting in a total of n * m iterations. The statement(s) inside the inner loop, denoted as “//Statement(s) that take(s) constant time,” are executed n * m times in total.

In the time complexity analysis, the expression n((2m+2) + cm) represents the total running time of the inner loop, considering the constant time statements. The additional terms 2n+2 account for the initialization, increment, and test of the outer loop.

The time complexity is determined by the dominant term, which in this case is nm(2+c). The 4n+2 term can be ignored as it is of lower order compared to nm(2+c). Therefore, the overall time complexity is O(nm).

To clarify, the initialization var j = 0 is indeed performed for each iteration of the outer loop, as j is re-initialized to 0 in the inner loop declaration. The inner loop executes m times per outer loop iteration.

I hope it helps. Happy Learning :blush:

2 Likes

Thank you! Realised this was a obvious answer question after reading the article a bit further on. But thank you so much for the detailed response!

1 Like