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 //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$