Python string comparisons time complexity-CodePudding

I'm curious how Python performs string comparisons under the hood. For example if

if s1 == s2:
   print(True)
else:
   print(False)

is the same as

condition= True
for x,y in zip(s1, s2):
    if x != y:
        condition = False 
print(condition)

Perhaps under the hood python is able to use ord values more efficiently than O(n) traversals?

CodePudding user response：

A simple test:

s1 = "a"
s2 = "aa"
condition= True
for x,y in zip(s1, s2):
    if x != y:
        condition = False 
print(condition) # True

show that your assumption is incorrect.
Otherwise, python == is very efficient, so you can assume it's at worse O(n).

CodePudding user response：

Regardless of how it's implemented, the comparison of two strings is going to take O(n) time. (There might exist pre-built side data structures that could help speed it up, but I'm assuming your input is just two strings and nothing else.)

Yes, the C implementation that == ends up calling is much faster, because it's in C rather than as a Python loop, but its worse-case big-Oh complexity is still going to be O(n).

PS: as @AdvMaple pointed out, your alternative implementation is wrong, because zip stops as soon as one of its input runs out of elements, but that does not change the time-complexity question.