0

I was doing a practice problem that involved concatenating strings in a for loop. I saw some info on older related questions on this site, but I wanted to know some other details. The book I got the practice problem from (Cracking the Coding Interview) did the solutions in Java. Here is a simplified version of the code just to get the point across:

for(int i = 0; i < str.length; i++){
   string += str.charAt(i) + i;
}

The book pointed out how this is slow because string concatenation in Java operates in O(n^2). And the solution to this was to use the StringBuilder class in java.

However, how would this work in Javascript? Does string concatenation using "+=" also work in O(n^2) time?

Ann Kilzer
  • 1,266
  • 3
  • 16
  • 39
frownyface
  • 153
  • 1
  • 8
  • 2
    No, in every (practical) JavaScript engine that works in linear time. Some implementation examples from 2011: https://stackoverflow.com/questions/7299010/why-is-string-concatenation-faster-than-array-join – Ry- Sep 21 '19 at 01:08

1 Answers1

1

To clarify, let's break apart the runtime complexity between the String concatenation and the for loop. String concatenation in Java is O(n) because Java creates an entire new string. Since you've put it inside a for loop, now we multiply another n to get O(n^2).

The string concatenation is not O(n^2), the concatenation inside the for loop is O(n^2).

In JavaScript, string concatenation works differently, and to further complicate it, the underpinnings are browser dependent. Here's an article from 2010 that explains some of the differences. Many browsers optimize for string operations, too. Check out this related question on string concatenation.

Ann Kilzer
  • 1,266
  • 3
  • 16
  • 39