Time Complexity | Sololearn: Learn to code for FREE!
¡Nuevo curso! ¡Todo programador debería aprender IA Generativa!
Prueba una lección gratuita
+ 2

Time Complexity

Can anyone please tell me the time complexity of below code and how? for(int i = 1;i<n;i=i*2){ for(int j=1;j<i;j++){ } }

2nd Mar 2024, 5:40 PM
Jawahirullah
Jawahirullah - avatar
6 Respuestas
+ 4
NB‚Äé but the inner loop does execute when i > 1. That starts happening upon the second pass of the outer loop. I tried to reduce the inner loop series into O() terms, but my math is too weak. [The compiler would optimize such a loop into oblivion because there is no work being done inside. In that case it's O(0)!]
3rd Mar 2024, 5:22 AM
Brian
Brian - avatar
+ 2
In outer for loop variable i iterates from 1 to n times doubling it's value in each iteration so it will execute log‚āā(n) times and inner for loop is never executed because condition j<i will always give false,so inner for loop does not add to time complexity. For eg if value of n is 8 then the above code which is only the outer loop,will execute log‚āā(8)=3 times.
2nd Mar 2024, 5:56 PM
ūĚėēūĚėČ
ūĚėēūĚėČ - avatar
+ 2
Yes Brian you are right I mistakenly assumed j=i instead of j=1 in my head
3rd Mar 2024, 5:28 AM
ūĚėēūĚėČ
ūĚėēūĚėČ - avatar
+ 2
Oh yes that was error in thinking ‚Äěeach second‚Äú and can be replaced.
3rd Mar 2024, 9:14 AM
JaScript
JaScript - avatar
0
The outer loop performs n/2 (each second of n) iterations, and the inner loop performs i iterations for each iteration of the outer loop, where i is the current iteration count of the outer loop. The total number of iterations performed by the inner loop can be calculated by summing the number of iterations performed in each iteration of the outer loop, which is given by the formula sum(i) from i=1 to outerRange, which is equal to outerRange * (outerRange + 1) / 2 that equals to n/2 * ((n/2 + 1) / 2) = time complexity
3rd Mar 2024, 7:57 AM
JaScript
JaScript - avatar
0
JaScript, if you squint a little more you'll notice the outer loop incrementer does not add 2; rather it multiplies by 2. So log2(n) is correct, as NB‚Äé said, for the number of outer loop iterations. The total inner loop iterations is the sum of 0, 1, 3, 7, 15, ..., n/2. Now figure out the general expression of that series summation and it will lead to the complexity solution.
3rd Mar 2024, 9:05 AM
Brian
Brian - avatar