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