Time complexity for concatenating strings 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 ?
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.