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

Question

If I had a for loop like:

normalized_str = ''
for char in paragraph:
   if char.isalnum():
       normalized_str += char.lower()
   else:
       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?

Isn't `char` just a single character? There's no loop inside `isalnum()` when just checking 1 character. — Barmar, Sep 04 '21 at 20:48
What @Barmar said and also, consider the complexity of string concatenation. Strings are immutable, so you create a new one I each loop. — Mark, Sep 04 '21 at 20:49
@Barmar Yes that is true, that went over my head. Thank you for pointing it out! — Confucius, Sep 04 '21 at 20:52
@Mark Although I think there's an optimization: If the variable is the only reference to the string, `+=` may be able to reuse the string storage and append in place. — Barmar, Sep 04 '21 at 20:52
@Barmar I suppose we should expect such things from Python. Do you know if that's a documented feature of the language or implementation specific? Edit...[there's this](https://stackoverflow.com/questions/34008010/is-the-time-complexity-of-iterative-string-append-actually-on2-or-on) — Mark, Sep 04 '21 at 20:53
@Mark Probably just implementation-specific. I just discovered it by printing `id(s)` before and after doing `s += "x"`. Sometimes it's the same id, sometimes not. — Barmar, Sep 04 '21 at 20:57

score 0 · Accepted Answer · answered Sep 04 '21 at 20:50

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.

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

1 Answers1