1
$\begingroup$

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

concatenating strings

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 ?

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ Feb 26, 2020 at 19:53

4 Answers 4

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.

$\endgroup$
2
  • $\begingroup$ The expression $1+2+\dots+n$ doesn’t have any time complexity. Rather, you’re interested in its asymptotic rate of growth. $\endgroup$ Feb 26, 2020 at 8:41
  • $\begingroup$ 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. $\endgroup$
    – anion
    Feb 26, 2020 at 8:46
1
$\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.

$\endgroup$
0
$\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) $

$\endgroup$
-1
$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.