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