Search code examples
javastringcomplexity-theorystringbuilder

space complexity string builder

In the example below, if I take in a String s, would the space complexity be O(n) or O(1)? and if I were to append only vowels, would it still be O(n)?

String s = "dfgdfgdfga";
StringBuilder sb = new StringBuilder();
for (int i = 0;i <s.length(); i++) {
    sb.append(s.charAt(i));
}
return sb.toString();
Solution

  • Space complexity boils down to: how much "memory" will you need to store things?

    Your code intends to basically copy all contents of String s into StringBuilder sb. Again: copy all chars from a to sb.

    Of course that boils down to O(n), with n representing the fact that you need more memory when you copy more characters. If you start making selections, you still have O(n).

    O(1) means: constant requirements. Which is simply not possible (space wise) when talking about making a copy.