1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In simple terms, the issue is that $k = O(n)$, not $O(1)$. $\endgroup$ – Antonio Vargas Jun 14 '18 at 16:51
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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