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 and s[1:], formation of s[1:] will take O(n-1),O(1) from s 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