Skip to main content
3 of 4
added 142 characters in body
zkutch
  • 2.4k
  • 1
  • 8
  • 14

Summand inside sum is not depend on summation index, then pull it out and you have n−1 before log.

Addition 1.

I specially copy above @plop's comment in case to keep it:

The equation is not correct in general. For example, $i\ln(n)\in O(\ln(n))$, but $\sum_{i=1}^{n-1}i\ln(n)=\frac{n(n-1)}{2}\ln(n)\notin O(n\ln(n))$.

Now about error in this reasoning: it's mistake to write $i\ln(n)\in O(\ln(n))$, when $i$ is in range from $1$ to $n$. In such case $i$ is not constant, but dependent on $n$. Obviously for each $i$ we have such $j$ for which $i=n-j$, but, hope, is clear that sentence $(n-j)\ln(n)\in O(\ln(n))$ is false. There is also some other subtle and very important detail, which I'll write in next addition - I beg pardon for mentioned in comment below "nearest days", but I have it almost ready and "hope in nearest days I'll find time to write it down".

zkutch
  • 2.4k
  • 1
  • 8
  • 14