CODEWITHSUNDEEP
javastringbuilder
cs guy
cs guy

Reputation: 929

Why StringBuilder.append time complexity is O(1)

By amortized analysis, we know that N insertions with StringBuilder#append method take O(N) time. But here is where I get lost. Consider this where inputString is an input string from a user.

for (int i = 0; i < N; i++) {
   s.append(inputString); 
   // where s is an empty StringBuilder object at the beginning 
   // and inputString is the string that is taken from the user
}

Should this have time complexity of O(inputString.length * N), since append() copies the input string to the end of the StringBuilder N times? Why do we consider that append() takes O(1) time complexity whereas it should be considered as O(inputString.length)?

Nearly everywhere I check, it is considered as O(1), such as https://quora.com/What-is-the-complexity-of-Java-StringBuffer-append as well as What is the complexity of this simple piece of code?

Upvotes: 9

Views: 13621

Answers (3)

Elton Ballhysa
Elton Ballhysa

Reputation: 1

It depends on what you are counting in your O(*) expression. If it is "the number of times a character is copied into the buffer array" then it has to be O(inputString.length * N) because the resulting buffer will have that many characters. However, in practice, what will dominate the running time is "the number of times a new byte[] is allocated" as you need larger buffers. If this is what you are counting, then the time complexity of append is amortized O(1), at the expense of (possibly) allocating more space than the resulting string needs. The implementation is almost the same as ArrayList#add being also "amortized" O(1). This is ultimately the difference between String concatenation and StringBuffer#append. Try this code for a deeper insight

StringBuilder buffer = new StringBuilder();
for (int i = 0; i < 10_000; i++) {
    buffer.append(<<some string value>>);
    System.out.println(buffer.capacity());
}

Upvotes: 0

yeoman
yeoman

Reputation: 1681

I guess we are talking about appending single characters. Appending a string of length N would have an O(N).

Answer: Because with increasing length, copying becomes less frequent by the same factor by which it becomes more expensive.

Let's assume the capacity doubles when full. Doesn't matter, could be a factor of 1.1, 3, or whatever, but it's easier to talk about.

Doubling 1 needs to copy 1000 chars, which on average over these first 1000 means 1 char to copy per char appended.

Doubling 2 needs to copy 2000 chars, which on average over the past 1000 after the first copy means 2 chars to copy per char appended.

Doubling 3 needs to copy 4000 chars, which on average over the past 2000 means 2 chars to copy per char appended.

Doubling 4 needs to copy 8000 chars, which on average over the past 4000 means 2 chars to copy per char appended.

&c.

So before the first doubling, it's free, then you pay half the price, and the the price settles at 2 chars per char appended on average.

Upvotes: 0

John Kugelman
John Kugelman

Reputation: 361585

Should this have time complexity of O(inputString.length * N) since append() copies the input string to the end of the StringBuilder N times?

Yes.

Why do we consider that append() takes O(1) time complexity whereas it should be considered as O(inputString.length)?

It is O(1) when appending single characters. A StringBuilder is like an ArrayList. When you append a single item the cost is O(1). Appending a string is like calling addAll()--the cost is proportional to the length of the string / the number of items being added.

It appears you understand everything correctly. The problem is people are often sloppy when discussing Big-O performance. It's endemic.

Upvotes: 24

Related Questions