How to think about $\sum_{k\leq t}k=\frac{t^2}{2}+\mathcal{O}(t)$

Question

I am looking for different ways to think of why the below equality holds:

$\sum_\limits{k\leq t} k=\frac{t^2}{2}+\mathcal{O}(t)$

Answer 1

So, using the standard formula $$\sum_{k=1}^{t}k=\frac{t(t+1)}{2}=\frac{t^2}{2}+\frac{t}{2}$$ we can see that the question is expecting you to see the link between the $t/2$ term and $O(t)$. So what does $O(t)$ mean? We say a function $f(t)$ is $O(t)$ if there is a (positive) constant $C$ such that $$ |f(t)|\leq Ct\ . $$ Here, our $f(t)=t/2$ and we can take any $C\geq 1/2$.

More generally, we say $f(x)=O\big(g(x)\big)$ if there is a constant $C$ (normally positive, depending on context) with $$ |f(x)|\leq Cg(x) $$ for all $x>0$ (again, depending on context).

Here are a few examples:

$$ \begin{array}{rcll} f(x)&=&O(f(x))& \text{always true, just take }C=1\\ x&=&O(x^n)&\text{for any }n\geq 1\text{ and }x\geq 1\\ x^n&=&O(e^x)&\text{for any }n>0\text{, so long as it is understood }x\geq 0\\ \sin x&=&O(1)&\text{in fact, any bounded function is }O(1) \end{array} $$