Simple query about time complexity for Python "in"

Question

I have a function strip_punctuation(text) which takes in a string of text and removes all punctuation in it using a punctuation list. I am not sure about the time complexity whether it is O(N)*N or O(N^2). I think that it works where it is O(N) for N text length, and then O(N) for length of punctuation. May someone clarify the time complexity for this code?

def strip_punctuation(text):
    punctuations = '''!()-[]{};:'"\,<>./?@#$%^&*_~'''
    stripped = ""
    for i in text:
        if i not in punctuations:
            stripped = stripped + i

    return stripped

I do notice that string concatenation in iteration (stripped = stripped + i) is not recommended and is consider O(N^2) in some style guide. — Blownhither Ma
– Blownhither Ma, Commented May 3, 2018 at 4:12
O(n^2) is probably right. Look at the maketrans() and translate() functions in the standard library (exact details depend on the Python version you're using), they can almost certainly do this job faster (if only because the loop over characters is written in C instead of Python). — jasonharper
– jasonharper, Commented May 3, 2018 at 4:47

zvone · Accepted Answer · 2018-05-03 05:57:29Z

1

If N is len(text), then this is O(N):

for i in text

If M is len(punctuations), then this code is O(M^2):

if i not in punctuations:
    stripped = stripped + i

That is because the whole stripped (which has length >= M) has to be copied M times (stripped + i makes a copy of stripped).

So, if both text and punctuations were inputs, the complexity would be O(N) * O(M^2), but in this case, M is a constant, so the complexity is O(N).

Note that if punctuations was very very big, the function would be very very slow, but its complexity would still be just O(N), which only means that it is N times slower when the input is N times bigger.

edited May 3, 2018 at 5:57

answered May 3, 2018 at 5:34

zvone

19.5k5 gold badges53 silver badges85 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Simple query about time complexity for Python "in"

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related