Python: A doubt on time and space complexity on string slicing

Question

This qns is from my school's exam paper.

Context: In a game of Hangman, player tries to uncover a hidden word by guessing the letters in the word. Assume all words and letters are lowercase.

The function remove takes as inputs 2 strings, a letter and a word, and outputs the word with all occurrences of letter removed.

Provide an iterative implementation of the function remove and briefly explain the time and space complexity of the function you have written.

Attached below was my code, which is the same as the solution provided.

However I got stumped when I tried to explain the time and space complexity as O(n) and O(1) respectively as the answer given was O(n^2) and O(n).

The explanation provided by the examiner is:

Time complexity: O(n^2) where n is the length of the input string. This is because in every loop iteration, the string concatenation of new_word gets longer until it is at worst, length n.

Space complexity: O(n), even though there are no delayed operations or new objects being created every iteration, the new string created at worst can be the same length as the original string if there are no letters removed.

My practice is when I explain something, I should be able to map it out mathematically.

Time: Sum of time taken for each iteration OR Sum of time for each recursion

1)I do not understand why string concatenation contributes to time complexity. For recursive codes its clear cut as there is string slicing involved(s[0] and s[1:], formation of s[1:] will take O(n-1),O(1) from s[0] is negligible) in every recursive call, sum of time is n+(n-1)+...+1=O(n^2). For the explanation of iterative, should I just accept it or is there a theory behind why concatenation adds to time complexity.

Space: Sum of space taken for each recursion OR sum of space taken for each iteration

2) I initially thought space for recursion and iteration is calculated the same way. Is it correct to accept that for iteration, space should be calculated as the space needed for the most demanding iteration instead of the accumulative sum of space for all iterations. Most demanding would then be when new_word and word are equivalent.

3) I actually accepted the fact that iteration usually takes up O(1) space and would bomb it everytime I can. What is really the reason behind deeming the space complexity of iterative to be O(1)?

Correct me at any point as I find that I am memorising and not understanding many things at this point.

def remove(letter,word):
 new_word=""
 for i in word:
 if letter!=i:
 new_word+=i
 return new_word

Answer 1

The running time of string concatenation depends on how it is implemented. It is impossible to tell whether new_word += i takes $O(1)$ or $\Theta(|\text{new_word}|)$ or anything else unless you know more about Python. Moreover, looking around stackoverflow, it seems that the complexity depends on which version of Python you are using.

In contrast, it is quite clear that the procedure uses $\Theta(|\text{word}|+1)$ space, since it builds new_word from scratch, not reusing the memory of word. This has nothing to do with the loop; the statement new_word = word[:], which makes a copy of word, also uses up $|\text{word}|$ space. Space consumption is the amount of memory used. If you're constructing a new string of length $|\text{word}|,ドル then it uses up memory proportional to $|\text{word}|$.

I suggest forgetting about what you call the "mathematical perspective", and focusing instead on the intuitive meaning of time and space complexity. Time complexity is the number of instructions executed by the program. Space complexity is the amount of memory that needs to be allocated in order to run the procedure. You are stating some rules for calculating these quantities, but it's much more important for you to understand what you are calculating rather than specific tricks which are dubious when applied mechanically.

• Prashin Jeevaganth: Thanks for the prompt reply. I would think what you are saying is that if a new sequence would to be formed(esp from scratch), the space complexity should be proportional to the length of the sequence.