Space complexity O(1) storing string

Question

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")}

Dewitt

Answer 1

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!

Gerdy

Answer 2

The above code mentioned looks like Python, but I will answer this question in the perspective of Java

public static void main(String[] args) {
        String s= "";
        char a='a';
        for(int i=0; i<26; i++){
            s+=(char)(a+i);
        }

        System.out.println(s);
    } 

Output: abcdefghijklmnopqrstuvwxyz

In the above code we feel like String s is been updated by adding each character at the end when each time loop runs, but internally new object is been created and old one will be left unreferenced in heap(which will later remove by garbage collection) but this cost an complexity of O(n²)

as each character is added in each loop but entire data is copied and created new object: 1+2+3+....+n=(n(n+1))/2 => O(n²)

In some cases, they can use more efficient mechanisms, such as StringBuilder, to minimize the creation of unnecessary intermediate String objects.

Anyone explain how it works in Python

Rotterdam