In my text, I am given that the sum of the first n positive integers can be understood in terms of big-O notation.
''Since each of the integers in the sum of the first $n$ positive integers does not exceed $n$'', we can write:
$$1 + 2 + \cdots + n \leq n + n \cdots + n= n^2$$
Why does $n + n +\cdots + n = n^2$ ?
On
To see why $n+n+...+n=n^2$, consider this:
The multiplication of two whole numbers is equivalent to the addition of one of them with itself as many times as the value of the other one; for example, 3 multiplied by 4 (often said as "3 times 4") can be calculated by adding 4 copies of 3 together:
$3 \times 4 = 3 + 3 + 3 + 3 = 12$
(Source: http://en.wikipedia.org/wiki/Multiplication)
Remember the explanation of multiplication you learned back in grade school! Ask yourself why we say 3 times 4... the wording is not arbitrary - we are literally adding 3, 4 times. Equivalently adding $n$ copies of $n$ is equivalent to saying $n$ times $n$, or $n^2$.
On
1+2+3+...+n is always less than n+n+n...+n n times. you can rewrite this n+n+..+n as n*n.
f(n) = O(g(n)) if there exists a positive integer n0 and a positive constant c, such that f(n) ≤ c * g(n) ∀ n ≥ n0
since Big-Oh represents the upper bound of the function, where the function f(n) is the sum of natural numbers up to n.
now, talking about time complexity, for small numbers, the addition should be of a constant amount of work. but the size of n could be humongous; you can't deny that probability.
adding integers can take linear amount of time when n is really large.. So you can say that addition is O(n) operation and you're adding n items. so that alone would make it O(n^2). of course, it will not always take n^2 time, but it's the worst-case when n is really large. (upper bound, remember?)
Now, let's say you directly try to achieve it using n(n+1)/2. Just one multiplication and one division, this should be a constant operation, no? No.
using a natural size metric of number of digits, the time complexity of multiplying two n-digit numbers using long multiplication is Θ(n^2). When implemented in software, long multiplication algorithms must deal with overflow during additions, which can be expensive. Wikipedia
That again leaves us to O(n^2).
We have that:
$$n+\underbrace{\cdots}_{n-2}+n=n^2=n\times n$$
from simple arithmetic (multiplying $n$ by $m$ can be viewed as adding $m$ lots of $n$). With regards to the validity of the statement $\sum_{i=1}^{n}i<n^{2}$ we can examine the closed form for the summation:
$$\sum_{i=1}^{n}i=\frac{n(n+1)}{2}=\frac{1}{2}(n^{2}+n)$$
We can see that this is strictly less than $n^2$ for $n> 1$ by observing that $n<n^{2}$ for $n>1$ and that $\frac{1}{2}(1^{2}+1)=1$ so the inequality does not hold for $n=1$.