CODEWITHSUNDEEP
javastringcomplexity-theorystringbuilder
Curious G
Curious G

Reputation: 47

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();

Upvotes: 4

Views: 3073

Answers (2)

noobCoder
noobCoder

Reputation: 322

Each time you append the StringBuilder it checks if the builder array is filled, if required copies the contents of original array to new array of increased size. So the space requirement increases linearly with the length of String. Hence the space complexity is O(n).

It does not matter if the letters are vowels, because the String Builder stores characters and not references to characters.

Although you might be interested in creating an implementation of String Builder that stores references to Character objects, but then it is more expensive to store references than the chars and also StringBuilder is final.

Upvotes: 2

GhostCat
GhostCat

Reputation: 140573

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.

Upvotes: 6

Related Questions