0

I need help in counting the number of steps regarding the time complexity of code fragments.

total = 0
    i = 0
while i<3:
    j=0
    while j<3:
        total = total + 1
        j = j+1
    i = i+1
return total

I have the solution stating: 2+3*(2+3*3+2)+2 = 43

the first two lines from the top where total = 0 and i = 0, yes i know that each of them is 1 time step each therefore adding up gives me 2. for the while statement, I'm not sure how its obtained but since i<3, its 3 time step? and then j = 0 is 1 time step.

Now here's where i don't quite get it. if there is a nested i and j loop, how do i determine the time complexity? in the solution, i notice there is *(multiple) and I will appreciate if anyone could break it down in simpler terms for me.

Electric
  • 517
  • 11
  • 25

1 Answers1

1

Time complexity takes an argument. For example, O(n^2).

As it's written, I don't know what part of your function would change, so it's just constant, O(1).

Let's say the thing that i is compared to, 3 in this case, is what can change. Like your function is "do a j-thing three times for each i." In that case, you'll see that if you increase that variable, you'll add three more steps to the loop. That means the complexity would look like O(3n). Since we can remove constant multiples, it's just O(n).

What I just wrote is hypothetical, though. It depends on what varies in your function.

swagrov
  • 1,510
  • 3
  • 22
  • 38