Return to Answer

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".

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".

Addition for silent down voters.

Down voting without argumentation doesn't help neither OP, neither readers, nor writers and nor this site - I sincerely welcome anyone who openly criticizes any proposal I wrote. An open, professional discussion of issues and responsibility for own words is the best friend and helper in our work. Dear down voter, I thought for a long time before writing Addition 1., I even found similar considerations in well-known sources (let's not name them for now) - do you have something to say/write?

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

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".

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

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