My question is around the Space Complexity of updating a dictionary with an input string.

e.g. string = "thisisarandomstring", my_dict = dict()

Say we iterate over the input string, and for each character, we store and update the index of the latest character.

i.e.

for i in range(len(string)): 
    my_dict[string[i]] = i

Would the space complexity for the above be O(n)? Or O(1)?

In the question I am solving the solution says it is O(n), but the way I see it, we will store at most 26 characters in the dictionary, so should't it be O(1)? I can see that the number of updates would be dependent on the length of the input string, but does this impact the space? Since for every update, we replace what was the previous index of the seen before element.

CodePudding user response：

You are right, eventually we can store 26 different keys in dictionary, therefore space consumed by the dictionary will be constant, that is O(1). However you are creating a string variable that consists of n characters. The space complexity of storing a new string of length n is Θ(n) because each individual character must be stored somewhere. Therefore that may be the reason why it is indicated as O(n).

Btw, if we denote the space complexity (amount of space consumed) as f(n). Then f(n) ∈ O(1) indicates f(n) ∈ O(n). Therefore f(n) ∈ O(n) is not a wrong statement. Well, technically.