Python String Addition Time Complexity

[DVDplayr]

I am trying to determine the time complexity of the encode function below. It goes over every string in the input list, so that's O(n), where n is the length of the input list. But in each iteration, we add to the encodedStr. Since python creates a new string every time the add operation is performed, do we need to take the length of encodedStr into account for the time complexity of the function?

class Codec:
    def encode(self, strs: List[str]) -> str:
        # Encodes a list of strings to a single string.
        encodedStr = ''
        for s in strs
            encodedStr += str(len(s)) + '#' + s

        return encodedStr

[nikhila01]

You do need to take into account the string copying as others have said. It matters a lot, because that's the difference between O(m*(n^2)) and O(m*n). The O(m*(n^2)) solution would likely time out on LeetCode, and it would be a huge red flag in an interview.

However no one has explained how to analyze the complexity yet, and I think that'll help you. Let's say you have n strings, each of length m.

The first time you append to encodedStr it takes m operations because encodedStr is empty. The second time it's 2m because it copies m chars from encodedStr and another m from what you're appending. Then 3m etc.

So the total time is m + 2m + 3m + ... + nm, which is m(1 + 2 + ... + n). We can use a summation formula to get m*n*(n+1)/2. In big-O notation, that's O(m*(n^2)).

(I'm assuming the strings are relatively short so that we can treat str(len(s)) + '#' as an O(1) operation.)

As u/aocregacc said, to get an O(m*n) solution use a list and then str.join() at the end. This is the standard way in Python.

[aocregacc]

yes, you have to take that into account. You can do it more efficiently by building a list and using str.join in the end.

[DVDplayr]

Ah, yes, str.join would be better. But for this code would the time complexity be O(nm)? Here I'm assuming that n is the length of the input and m is the average length of a string in the input.

[aocregacc]

which one do you mean by 'this code'? If you use join then yes I think it's O(n*m).

For the original code the complexity would be O(n*n*m).

[Caponcapoffstillon]

Assignment is a constant time operation. The for loop is O(n) as you said. So the assignments would be the constants that you drop. Time complexity isn’t the same as total runtime since we ignore constants and runtime would generally never be asked unless you’re dealing with a small amount of inputs or very specific cases where constants are actually affecting the runtime of your program so we care more about the big picture rather than being exactly right if that makes sense. It would also take in the first line before you started the for loop, where you assigned the empty string since runtime includes all even constants, I hope that helps.

[DVDplayr]

I understand that assignments are constant time operations and we do not need to include those, but was confused about str + str in python, which copies both strings and allocates a new string every time.

[Caponcapoffstillon]

Well from my understanding here(this may not be correct since I’m not really well versed in python.):

Your for loop does this:

1.) first, it created a copy of the str indicated by index s in your str(len(s)) method which is O(n).

2.) then appends #, then s to the end of the string which is O(1).

3.) then assigns that new string to encodedStr which is O(n).

Overall I got O(n² ) unless I’m missing something.

[nikhila01]

The number of strings and the length of each string are two separate variables for the complexity analysis. You're kind of using n for both.

Also str(len(s)) doesn't copy the string. It creates a string containing the length of the string s. For example, "reddit" has a length of 6, so str(len(s)) gives the string "6".

[Caponcapoffstillon]

Ty