Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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();
like image 757
Curious G Avatar asked Oct 28 '25 04:10

Curious G


1 Answers

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.

like image 80
GhostCat Avatar answered Oct 29 '25 20:10

GhostCat



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!