# Time complexity for concatenating strings

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

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 ?

• As others have mentioned, the book claimed $O(x + 2x + ... + nx)$ complexity, which is different than $O(x + 2x + nx)$. However, your analogy might point out another misunderstanding. Could you elaborate on what you are trying to accomplish with it? Feb 26, 2020 at 19:53

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.

• The expression $1+2+\dots+n$ doesn’t have any time complexity. Rather, you’re interested in its asymptotic rate of growth. Feb 26, 2020 at 8:41
• Maybe it is couched imprecisely, sorry. Back to the joinWords-function from the question: If you copy 1 character, then copy 2 characters ... and in the end copy n characters then you have (n^2+n)/2 copy-steps which describes the time complexity of the joinWords-function here. Feb 26, 2020 at 8:46

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.

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

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.