stringconstantsbig-ocomplexity-theorynotation

Space complexity O(1) storing string

I am a bit confused on space complexity. Is this O(1) space complexity or O(N) complexity? Since I am creating a string of size n, my guess is the space complexity is O(N) is that correct?

## this function takes in a string and returns the string

def test(stringval):
stringval2 = ""   
for x in stringval:
   stringval2 = stringval2 + x
return stringval2

test("hello")}
Solution

  • Yes, that's correct. The space complexity of storing a new string of length n is Θ(n) because each individual character must be stored somewhere. In principle you could reduce the space usage by noticing that stringval2 ends up being a copy of stringval1 and potentially using copy-on-write or other optimizations, but in this case there's no reason to suspect that this is the case.

    Hope this helps!