8

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?

cs guy
  • 926
  • 2
  • 13
  • 33
  • That quora post says O(1) *amortised*, then goes on to carefully explain why. – jonrsharpe Jun 27 '19 at 22:26
  • Yes but I do not think that it takes the length of the inputString into account @jonrsharpe – cs guy Jun 27 '19 at 22:27
  • because the length of the string does not change, it is a constant. Constant factors a reduced to 1. – k5_ Jun 27 '19 at 22:29
  • 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 @k5_ , it is an input which varies just like N – cs guy Jun 27 '19 at 22:31
  • https://stackoverflow.com/a/7156703/2055998 - another opinion. – PM 77-1 Jun 27 '19 at 22:31
  • @k5_ That's wrong. `inputString` is a variable, therefore so is `inputString.length`. It must be factored in. – John Kugelman Jun 27 '19 at 22:38
  • 1
    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. – Erwin Bolwidt Jun 27 '19 at 22:42
  • @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 – cs guy Jun 27 '19 at 22:48
  • 1
    @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. – John Kugelman Jun 27 '19 at 22:51
  • 1
    @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. – Erwin Bolwidt Jun 27 '19 at 22:56
  • 1
    You said the maximum length of strings is 2^31-1, so technically O(n) string algorithms are O(1). That's a distraction. – John Kugelman Jun 27 '19 at 23:06
  • 1
    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. – John Kugelman Jun 27 '19 at 23:10

1 Answers1

21

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.

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
  • 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. – BevynQ Jun 27 '19 at 23:12
  • 1
    In what theoretical model is copying an array of size N O(1)? – John Kugelman Jun 27 '19 at 23:15
  • 1
    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) – Minn Jun 27 '19 at 23:15
  • 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. – BevynQ Jun 27 '19 at 23:36