Why StringBuilder.append time complexity is O(1)

Question

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?

Stubbs

That quora post says O(1) amortised, then goes on to carefully explain why. – Osier

Yes but I do not think that it takes the length of the inputString into account @Osier – Stubbs

because the length of the string does not change, it is a constant. Constant factors a reduced to 1. – Sastruga

Yes but it cleary effects the time taken by the algorithm, by the same manner I can say that N is a constant as well since its just a random number inputted by the user @Sastruga , it is an input which varies just like N – Stubbs

https://mcmap.net/q/434103/-what-is-the-complexity-of-this-simple-piece-of-code - another opinion. – Matilda

@Sastruga That's wrong. inputString is a variable, therefore so is inputString.length. It must be factored in. – Hemicycle

Complexity analysis is more of an art. If your input string length is the variable factor in your input data, and it can go to infinity, then you should take it into account. If your stated problem/algorithm gives an upper bound to the input string length, then it's a constant factor. But note that real machine almost always have limits to lengths because storage isn't infinite - Java limits strings to 2^31-1 characters, so technically it's always O(1). It depends on from which perspective you want to analyse your algorithm. – Gem

@ErwinBolwidt I get the intuition but still imagine where inputString.length is close to N then this algorithm would take O(N^2) time. Whereas if inputString.length was considered O(1) it should have been as considered as O(N) which is completely wrong, I do not think your interpretation is truly correct – Stubbs

@ErwinBolwidt Every computer system is finite. We don't acknowledge that in complexity analysis because it makes every algorithm O(1). It's a distraction to bring it up. – Hemicycle

@JohnKugelman No it isn't a red herring. It's fundamental. Big-O without further qualification is talking about N going to infinity. If N doesn't go to infinity, it's a constant factor. Whether the constant factor is close enough to infinity for practical purposes is important. If a CPU can do a memory copy of the maximum possible length of your data in little more than it takes to do a constant-time operation, then you should consider it O(1). If the difference is much bigger, you should consider it O(n). However here it's more important whether the problem limits the length of the input. – Gem

You said the maximum length of strings is 2^31-1, so technically O(n) string algorithms are O(1). That's a distraction. – Hemicycle

The question doesn't mention any limitation on the size of inputString so I don't know why one's being imagined. You could do that with any variable in any Big-O analysis ever. "Well, if the size of an array is bounded, then technically O(n log n) sorting is O(1). Oh, and if the size of a linked list is bounded then technically O(n) search is O(1). Oh, and..." Why say those things? They're pointless statements. – Hemicycle

Answer 1

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.

Hemicycle

A) I don't need a concrete example as O notation is theoretical, so we deal with theoretical models. B) concrete world example 64bit number is an 8 element array of 8 bit numbers. copying 1 byte takes 1 cycle copying one qword takes 1 cycle. You cannot make assumptions about how an underlying function works. – Monied

In what theoretical model is copying an array of size N O(1)? – Hemicycle

That just makes it n/k where k is a constant factor of how big the chunk is that can be copied. That is still O(n) – Expressly

You are missing the point Algorithmic efficiency is not about real world performance it is entirely theoretical. For O notation k = infinity is valid. An array copy could just be a pointer change or it could be a bit by bit transportation using hamsters. It could be glacial or it could be instantaneous, When designing an algorithm we don't know and we cannot know so it is irrelevant. I repeat you cannot make assumptions about how an underlying function works. – Monied