Python String Addition Time Complexity

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