8

I'm planning to perform lots of deletes of the last character in StringBuilders. The solution to use sb.setLength(sb.length() - 1); looks good to me. However, since these deletions will be in a loop, I need to know complexity of it.

The way I understand it is that this operation simply decrements some private attribute of my StringBuilder object and does not perform any copying/cloning/duplicating of the characters themselves, thus it is O(1) in time and should work fast.

Am I right?

Improve this question
1
  • 4
    If you program Java, you should be using an IDE, and it should allow you to see source code of most Runtime Library classes, so with 1 minute of research time, you should have been able to answer this question yourself. Commented Jan 31, 2016 at 5:54

3 Answers 3

Reset to default
10

It's O(1) if the new length is less than the old one, which it is in your case.

The JDK's source code is available online, so you can check it for yourself. Using Java 8 as an example, setLength is implemented in AbstractStringBuilder. It does a few things:

  • errors if the new length < 0
  • ensures that the StringBuilder has enough capacity for the new length (which it will, if you're shortening the length)
  • fills in 0s for the additional length, if you're extending the length (which you're not)
  • sets the this.count field to the length you specify

Putting it all together:

  • If you're shortening the length, this is O(1) — a few quick checks and then a field assignment.
  • If you're increasing the length, but such that the old capacity is still sufficient, then it's O(N) where N is the additional length (for instance, if you had a 100-length builder, then shortened it to 10, and are are now increasing it to 90, then N would be 90-10=80)
  • If you're increasing the length such that the capacity needs to be increased, it's O(N) where N is the new capacity
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

In addition to source being available online, you also get a copy when installing the JDK, and a good IDE will automatically use it, so you can see source code of most Runtime Library classes (e.g. if using Eclipse, press F3 when on class or method).
4

From the documentation:

Sets the length of the character sequence. The sequence is changed to a new character sequence whose length is specified by the argument. For every nonnegative index k less than newLength, the character at index k in the new character sequence is the same as the character at index k in the old sequence if k is less than the length of the old character sequence; otherwise, it is the null character '\u0000'. In other words, if the newLength argument is less than the current length, the length is changed to the specified length. If the newLength argument is greater than or equal to the current length, sufficient null characters ('\u0000') are appended so that length becomes the newLength argument.

The newLength argument must be greater than or equal to 0.

I would say yes. But I wouldn't see it from the point of view of time complexity. The reason we use StringBuilder instead of String in a loop is because Strings are immutable. Hence a new string object will always be created when we try to change it. When you change the length of a StringBuilder object, no new object is created.

Improve this answer

1 Comment

This answer is misleading as if the new length is larger than the current length of the underlying array it will require a full copy of the previous array. I find @yshavit's answer more accurate
4

Complexity of setLength differs from operation ( increase or decrease ) complexity of increase operation is not O(1), I think it is O(n), because, in this operation new array will be generated, and each unused byte of stringbuilder with replaced by '\0' byte

But decrease operation is O(1) complexity , because of that in this operation only count of characters will be changed.

There is source of setLength method in StringBuilder class source file
http://developer.classpath.org/doc/java/lang/StringBuilder-source.html

 225: public void setLength(int newLength) 226: { 227: if (newLength < 0) 228: throw new StringIndexOutOfBoundsException(newLength); 229: 230: int valueLength = value.length; 231: 232: /* Always call ensureCapacity in order to preserve copy-on-write 233: semantics. */ 234: ensureCapacity(newLength); 235: 236: if (newLength < valueLength) 237: { 238: /* If the StringBuilder's value just grew, then we know that 239: value is newly allocated and the region between count and 240: newLength is filled with '\0'. */ 241: count = newLength; 242: } 243: else 244: { 245: /* The StringBuilder's value doesn't need to grow. However, 246: we should clear out any cruft that may exist. */ 247: while (count < newLength) 248: value[count++] = '\0'; 249: } 250: }
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.