This question already has an answer here:
- Big-O notation and polynomials 2 answers
This problem is an example in a Discrete Math textbook. How can big-O notation be used to estimate the sum of the first n positive integers?
Solution: Because each of the integers in the sum of the first n positive integers does not exceed n, it follows that $$1+2+...+n \le n+n+...+n=n^2$$ From this inequality it follows that $1+2+...+n$ is $O(n^2)$.
I do not understand how the sum of $n$'s is equal to $n^2$. Can anyone explain to me what the book used to get this?