Time complexity of loop statement using isalnum() (Python)

If I had a for loop like:

normalized_str = ''
for char in paragraph:
   if char.isalnum():
       normalized_str += char.lower()
       normalized_str += ' '

this is basically just going through a long paragraph string and concatenating all the words and ignoring punctuations (besides the point but just as an overview).

Would the time complexity of this be O(n^2)? I believe the time complexity for the isalnum function is o(n) since it will go through each character to check if its an alphanumeric and we iterate over n words.

Since at each iteration of the for loop, we do an o(n) operation, does this make it O(n^2)? Or just a 2-pass O(n) time complexity?


No, it would still be O(n). It would only be O(n^2) if it was checking against itself in some way. Lets say the lookup is in a hashset with constant lookup times O(1). Then complexity is obviously O(n).

Now lets say the lookup has O(n), where n the alnums, itself. It’s n does not change if I got your question right, which makes it constant. So the overall complexity is also O(n), as it relies on a constant.