0

I'm trying to understand why String Concatenation is O(n) time complexity in Java. We were told that s1 + s2 is going to both create a new string with length of s1.length() + s2.length(), and copy s1 and s2 into that new string. So the following cost was calculated (by them) 2 + 2(n+1) + 1 => (5 + 2n)

I'm not sure I understand how my lecturers got that calculated. Would anyone mind explaining the operations of string concatenation to me that justifies the above mentioned cost?

JakeDrone
  • 173
  • 1
  • 9
  • what would you say `5+2n` in terms of complexity is? – Naman Oct 21 '20 at 07:27
  • @Naman I understand that `5 + 2n = O(n)`, I don't understand how they got to `5 + 2n` though. Is the string `s1` and `s2` being looped and assigned character for character to a new string? – JakeDrone Oct 21 '20 at 07:28
  • so **if** both the strings are length `n`, you would have `n` characters walkthrough of each string meaning `2n`, about those constant operations, maybe finding their length is what the other person might have termed as `2` and then something similar for the rest of the `3`..showing the code might just be worth it. – Naman Oct 21 '20 at 07:40
  • The actual implementation may copy multiple characters at once using low-level operations, but in principle yes, it has to copy each character from both strings. – kaya3 Oct 21 '20 at 07:41
  • Thanks to both of you, that was helpful. – JakeDrone Oct 21 '20 at 07:48

1 Answers1

0

I would be careful making assumptions regarding what is happening during String concatenation in Java since it changed internally starting with Java 9.

A good presentation regarding this topic can be found here: https://www.javaspecialists.eu/talks/pdfs/2018%20Voxxed%20in%20Thessaloniki,%20Greece%20-%20%22Enough%20java.lang.String%20to%20Hang%20Ourselves%20...%22%20by%20Heinz%20Kabutz.pdf

Also worth reading: https://dzone.com/articles/jdk-9jep-280-string-concatenations-will-never-be-t

And already a bit older but maybe relevant to you: https://stackoverflow.com/a/15401136/875083

Joachim Rohde
  • 5,915
  • 2
  • 29
  • 46