What is the time complexity of string concatenation javascript?

I am learning algorithms. And I didn't find any articles about how to calculate Time Complexity of string concatenation in JavaScript.

function concatString(str1, str2) {
  // return str1 + str2;
  // return str1.concat(str2)
}

We can concat strings using operator '+' or using built-in method String.prototype.concat

Which method is better? What is the Time Complexity of both methods?

• javascript
• string
• time-complexity
• string-concatenation

asked Sep 4, 2021 at 17:12

17

• If you don't have an actual performance issue that you've determined involves string concatenation efficiency, then worrying about it is a waste of time.

  Sep 4, 2021 at 17:21

• I am learning algorithms. And I didn't find any articles about how to calculate Time Complexity of string concatenation in JavaScript. That is why my function is such simple.

  Sep 4, 2021 at 17:26

• @Pointy I'm going to disagree with you there - we should be encouraging mental curiosity, not punishing people for asking questions-we-feel-people-shouldnt-ask.

  Sep 4, 2021 at 17:34

$\begingroup$

I was going through this piece of code from an algorithms books and something doesn't look clear

Please ignore the spelling errors,

How does 0(x + 2x + nx) reduce to o(xn^2) ?

My analogy, assuming x is a constant 1 and n is 2 (x + 2x) == 3 assuming x is a constant 1

From the book (x2^2) == 4 assuming x is a constant 1

Am i right ?

asked Feb 26, 2020 at 7:34

$\endgroup$

1

$\begingroup$

How does O(x + 2x + nx) reduce to O(xn^2) ?

O(x + 2x + nx) will be reduced to o(xn). But as your text says O(x + 2x + ... + nx) will be reduced to o(xn^2). (So if you have n = 5 for example you have the time complexity O(1x + 2x + 3x + 4x + 5x) which is equal to O(15x).) The time complexity of 1 + 2 + ... + n is O(n^2) (since 1 + 2 + ... + n = (n^2+n)/2, see my comment below). But in your case every addend in the sum must be multiplied with x, so you have O(x*n^2) as final result.

answered Feb 26, 2020 at 8:38

anionanion

2161 silver badge3 bronze badges

$\endgroup$

2

$\begingroup$

The author did not say

$$x+2x+\cdots+nx=n^2x.$$

He said

$$x+2x+\cdots+nx=\frac{n(n+1)}2x$$ so that

$$x+2x+\cdots+nx=O(n^2x).$$

If you don't know the meaning of the asymptotic notation $O$, read https://en.wikipedia.org/wiki/Big_O_notation.

Notice that $1+2=\dfrac{2\cdot(2+1)}2$ is quite right.

answered Aug 14 at 19:12

Yves DaoustYves Daoust

5,23512 silver badges30 bronze badges

$\endgroup$

$\begingroup$

Here, Big $ O $ notation refers to the asymptotic upper bound to the running time as a function of input length. A formal definition and reference can be found here. As $ n^2 $ is a satisfactory upper bound to the function $ \frac{n(n+1)}{2} $ , the running time which comes out as $ \frac{n(n+1)}{2} $ can be expressed as $ O(n^2) $

answered Feb 26, 2020 at 8:59

SiluPandaSiluPanda

4993 silver badges10 bronze badges

$\endgroup$

$\begingroup$

We can't say what the time complexity is, because it depends on the implementation. There is no good reason why making a copy of a string with n characters should take O(n), and not O(1). Actually, implementors of standard libraries and languages will work hard to make sure the time is O(1).

I would be reasonably sure that equivalent code in Swift would run in O (xn). At least if we replace "sentence = sentence + w" with "sentence.append(w)", and a clever compiler can do that.

answered Jul 25, 2020 at 12:27

gnasher729gnasher729

25.9k30 silver badges40 bronze badges

$\endgroup$

Is string concatenation slow?

Is concatenation faster than join?

What is JavaScript string concatenation?

What is the best way to concatenate strings in JavaScript?