CODEWITHSUNDEEP
pythontime-complexitybig-ocomplexity-theory
pmaen
pmaen

Reputation: 85

Big O notation of if inside while-loop

I have this code and I need to figure out its Big O notation but I'm very unsure about it. My idea was that it should be some large integer times n because everything but the while-loop should be constant. Hence it would be O(n). Is that correct?
(I know that the code does not make sense. I have changed it so that its actual purpose is no longer recognizable. So c==3, d==4, e==5 and f==6 aren't always true.)

a,b,i = 3,0,0
mystring = input("Input your string")
if a == 3:
    print(a)
else:
    print("a is not 3")
while (b < 10) and (i < 4*len(mystring)):
    c,d = 3,4
    if (c==3 and d==4):
        e,f = 5,6
        if (e==5 and f==6):
            print("good so far")
            b +=1
        else:
            i +=1
    else:
        i +=1
if i >= 4*len(mystring):
    print("maximum reached")
else:
    print(i)

Upvotes: 1

Views: 326

Answers (1)

kaya3
kaya3

Reputation: 51162

The conditions c == 3 and d == 4 and e == 5 and f == 6 are both always true, since the lines immediately before them set these variables to these exact values. So we might as well write it like this, because it does the same thing:

while b < 10 and i < 4 * len(mystring):
    c, d = 3, 4
    # (c == 3 and d == 4) is True
    e, f = 5, 6
    # (e == 5 and f == 6) is True
    print("good so far")
    b += 1

Hopefully it is now obvious that this loop iterates at most 10 times, because b increases by 1 on every iteration and the loop terminates when b reaches 10 (if not sooner). So the overall time complexity is Θ(1).

Upvotes: 2

Related Questions