Java StringBuilder.setLength () - is O (1) time complexity?

Question

I plan to do many deletions of the last character in StringBuilders. Solution to use sb.setLength(sb.length() - 1); looks good to me. However, since these deletes will be in a loop, I need to know its complexity.

I understand that this operation simply reduces some private attribute of my StringBuilder object and does not do any copy / clone / duplication of the characters themselves, so this is O (1) in time and should work quickly.

I'm right?

Answer 1

From the documentation:

Sets the length of a sequence of characters. The sequence changes to a new sequence of characters, the length of which is specified by the argument. For each non-negative index k less than newLength, the character with index k in the new character sequence is the same as the character with 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 argument newLength is less than the current length, the length changes to the specified length. If the argument newLength is greater than or equal to the current length, sufficient null characters ('\ u0000') are added, so that the length becomes the argument newLength.

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

I would say yes. But I would not see this in terms of the complexity of time. The reason we use StringBuilder instead of String in a loop is because strings are immutable. Therefore, a new new object will always be created when we try to change it. When you change the length of a StringBuilder object, a new object is not created.

Answer 2

This is O (1) if the new length is less than the old, which is in your case.

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

• if new length <0
• ensures that StringBuilder has enough capacity for the new length (which will happen if you shorten the length)
• fills 0s for extra length if you extend the length (which you are not)
• sets the this.count field to the length you specify

Putting it all together:

• If you shorten the length, this is O (1) - a few quick checks, and then the purpose of the field.
• If you increase the length, but so that the old capacity is still sufficient, then O (N), where N is the extra length (for example, if you had a builder with a length of 100 lines and then reduced to 10, and now they increase it to 90 then N will be 90-10 = 80).
• If you increase the length to increase the capacity, then O (N), where N is the new capacity.

Answer 3

The complexity of setLength is different from the operation (increase or decrease) the complexity of the increase operation is not O (1), I think it is O (n), because in this operation a new array will be generated, and each unused byte of the string editor with the replacement by '\ 0 'byte

But the reduction operation is O (1) complexity, because of which only the number of characters will be changed in this operation.

There is a source for the setLength method in the source file of the StringBuilder class
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 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 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: }