An argument involving big-O notation

Question

I came across the following argument in my discrete maths textbook:

Since $n=O(n), 2n=O(n)$ etc., we have: $$ S(n)=\sum_{k=1}^nkn=\sum_{k=1}^nO(n)=O(n^2) $$

The accompanying question in the book is: What is wrong with the above argument?

Attempt: Performing the summation for $n=2,3$ gives: $$ \sum_{k=1}^2k(2)\leq\sum_{k=1}^22(2)=2(2^2)=O(2^2) $$ $$ \sum_{k=1}^3k(3)\leq\sum_{k=1}^33(3)=3(3^2)=O(3^2) $$ Thus, it seems like the argument is correct. However, I know that I am not correct.

Answer 1

It is a problem of quantifiers $f(n)=O(n)$ means that there exists a constant $M$ that is independant of n such that for all $n$ large enough $|f(n)| \le Mn$. In your case, the implied constant for each term is $k$, which does depend on $n$ since it ranges between $1$ and $n$. So you cannot get this way an implied constant for the sum that does not depend on $n$.

Answer 2

$k$ is a variable that runs from $0$ to $n$, therefore in the small cases your textbook showed you, it appears to be $O(n)$, however, the ending terms of the sum are $..., (n-2)n, (n-1)n, n^2$ which are clearly not $O(n)$. Therefore, the argument of the sum is not $O(n)$ but rather ${O(n)}^2$. This means that the sum in question, once evaluated, is $O(n)^3$.

Answer 3

Assuming that we have $$ O(kn) $$ using your logic, then we can say if $n<5$ then choosing $k = 10$ we are saying that $$ kn > n^2 \;\;\forall\; n $$

alternatively if I have $k=2$ then $$ kn < n^2 \;\;\forall \;n > 2 $$ so by choosing a fixed parameter we changing when $n^2$ is less than $kn$ this could be generalised to $$ n^2 < kn \;\; \forall \;n > k $$ this is the case when we assume that we have some notion of what $n$ is w.r.t $k$. However, the whole point of this notation is that we are saying that we have some linear relationship with the order of the iterations. If we keep letting $n$ increase regardless of $k$ (which is a constant) then we will eventually have a value of $n^2 > kn$ no matter what value of $k$ is. The big-oh notation signifies the relationship on $n$ and how the calculation scales with $n$.

To summarise if $k$ is constant then we will reach a point where $$ O(kn) < O(n^2) $$