1

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)
pmaen
  • 43
  • 5
  • 1
    First of all, you shall define what `n` is. – Alessandro Cosentino Feb 20 '22 at 10:31
  • Does this answer your question? [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Mark Rotteveel Feb 20 '22 at 10:31
  • @AlessandroCosentino I'm not sure how to do that, because both `b` and `i` are relevant for the loop. – pmaen Feb 20 '22 at 15:57
  • @MarkRotteveel Unfortunately it doesn't because I don' really know how to apply what they are doing there to my code. – pmaen Feb 20 '22 at 15:58
  • @pmaen It's not about the indices of the loop, whereas it is about the inputs of your algorithm. Say you had to write this snippet as a function, which one would be a variable input of the function? The string `mystring` perhaps? The way it's written now, everything is of constant size, so it's difficult to argue about asymptotic behavior, which is what you do when you use the Big-O notation. – Alessandro Cosentino Feb 20 '22 at 16:55
  • 1
    @AlessandroCosentino Thanks for the explanation. Then `mystring` would be `n`. – pmaen Feb 21 '22 at 17:39

1 Answers1

2

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).

kaya3
  • 47,440
  • 4
  • 68
  • 97
  • In the real code these statements aren't always true. – pmaen Feb 21 '22 at 17:40
  • @pmaen Sounds to me like you asked a question about different code than you actually wanted an answer about, then. You can't expect people to guess that the code you want an answer about is different to the code you actually wrote. – kaya3 Feb 21 '22 at 22:38