3
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by Antonio Vargas, ml0105, M Turgeon, apnorton, user61527 May 1 '14 at 17:16

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I'm confused as to why you'd want to estimate the sum of the first n positive integers since this is a well-known formula $\frac{n(n+1)}{2}$. $\endgroup$ – EgoKilla May 1 '14 at 1:54
  • $\begingroup$ How many "$n$"s are in the sum "$n+n+\cdots+n$"? $\endgroup$ – Eric Towers May 1 '14 at 1:55
3
$\begingroup$

The sum of $n$ $n$'s is $n \cdot n$, by definition. $n \cdot n = n^2$.

Also, Big-O notation is used for bounding, not estimation. As Big-O notation removes all constant multipliers and merely represents an upper asymptotic bound, it is not a useful estimator.

$\endgroup$
  • 1
    $\begingroup$ Maybe "\cdot" ? $\endgroup$ – Eric Towers May 1 '14 at 1:56
  • $\begingroup$ Done. I am always too lazy to make that switch in my homework, but it's probably a bad habit I should break out of. $\endgroup$ – user2258552 May 1 '14 at 1:57
  • $\begingroup$ Thank you! This was an example problem in Rosen's Discrete Math book. I didn't really understand the purpose of the example but just needed to clarify that one step. $\endgroup$ – Kot May 1 '14 at 1:59
  • $\begingroup$ @user2258552 "Big-O notation removes all constant multipliers" was the key to understand this, thanks! $\endgroup$ – rgkobashi Jan 27 at 20:30
3
$\begingroup$

First, you note that$$1+2+\ldots+n = \frac{n^2+n}{2} $$ Since this is a quadratic polynomial, follows that it is $O(n^2)$.

$\endgroup$

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