0

I am studying a Big-O example but I just do not get the idea. I have already seen that this question was asked in this forum but I am still confused. Can someone please provide another explanation so I can have more options to analyze? My main question in the part that says "Because each of the integers in the sum of the first n positive integers does not exceed n". How can I get to this reasoning?

The problem is as follows:

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 ≤ n + n+· · ·+n = n2. From this inequality it follows that 1 + 2 + 3+· · ·+n is O(n2), taking C = 1 and k = 1 as witnesses. (In this example the domains of the functions in the big-O relationship are the set of positive integers.)

JORGE
  • 341

2 Answers2

0

[Assuming I understood what you need]: essentially you have a function $S(n)$ on LHS and $n^2$ on RHS and you ask youself, for which $n \geq n_0 $ and $c_1$ will $S_{n \geq n_0} \leq c n^2$. In a sense $ c n^2$ is an upper bound for the rate of growth of $S_n$.

Hence, first you bound the sum by $n^2$ and then notice that $n^2 \in O(n^2)$ with $c=1$ and $n_0=1$. Therefore, $S_n \in O(n^2)$.

Alex
  • 19,262
0

Have a read of the Wikipedia article on this.

Note the formal definition:

Let $f$ and $g$ be two functions defined on some subset of the real numbers. One writes

$$f(x)=O(g(x))\text{ as }x\to\infty,$$ if and only if there is a positive constant $M$ such that for all sufficiently large values of $x$, the absolute value of $f(x)$ is at most $M$ multiplied by the absolute value of $g(x)$. That is, $f(x) = O(g(x))$ if and only if there exists a positive real number $M$ and a real number $x_0$ such that

$$|f(x)| \le \; M |g(x)|\text{ for all }x \ge x_0.$$

You are looking for a function, which when multiplied by a constant is equal to or bigger (in absolute terms) then the function you are considering.

So here is your function:

$$1+2+\dots+n$$

This is always less than $1n^2$ by the argument you make so therefore the function is $O(n^2)$.

An alternative argument is:

$$\begin{align} \sum_{i=1}^ni&=\frac{n(n+1)}{2}\\ &=\frac{n^2}{2}+\frac{n}{2}\\ &\le Mn^2\\ &=O(n^2) \end{align}$$

Dale M
  • 2,813