educative.io

Educative

Time complexity for question 9

Hi, I’m wondering why is the answer for this question is C?

My calculation is:

statement time
var value = 0; 1
for(var i=0;i<n;i++) 1 + (n+1) + n
for(var j=0;j<i;j++); n + (n(n-1)/2 +1)+ n(n-1)/2
value += 1; n(n-1)/2

The outer loop runs n times and the inner loop runs n(n-1)/2 times.
The inner loop will not run in the first iteration of the outer loop, then run once in the second iteration of the outer loop and then run twice for the third iteration of the outer loop, and so on. So we will use the following formula to calculate the complexity of the inner loop for all the iterations of the outer loop:

I hope this helps. Happy learning!

Maida Ijaz | Developer Advocate
educative.io

1 Like