What is the correct notation for simplifying O notation?

Question

For instance I want to say something like:

"Here is the resulting runtime:

$$\sum_{x}^{n}\sum_{y}^{x} (1) = \frac{n(n+1)}{2} \implies n^2 \implies O(n^2)$$"

But what is the proper way to state this in terms of notation?

Answer 1

The correct way to write it down would be

$$ f(n) = \frac{n(n+1)}{2} \sim n^2 \implies f \in \mathcal{O}(n^2)$$

Note that $\mathcal{O}(n^2)$ is a family of functions, so it does not make sense to write "="m but in fact, that is quite common to do it anyway.

Answer 2

The abuse of notation you're probably most familiar with is to use $f(n) = O(n^2)$ or equivalent. People tend to accept this as legitimate, but you're right in thinking that it's not the "right" notation depending on how it's defined. The more correct but less natural approach is to say $f(n) \in O(n^2)$. People will know what you mean in saying this, but it's not really how you want to use it when you're using it. In any case, both are appropriate and understood.

Answer 3

For $f(n)=O(n^2)$, we means that there exists a constant $C$ such that $$f(n)\leq C n^2.$$ Now, you have $f(n)=\frac{n(n+1)}{2}=\frac{1}{2}n^2+\frac{1}{2}n$. Since the highest degree of $n$ is $2$, one can find a constant $C$ (eg. $C=10$) such that $f(n)\leq Cn^2$, i.e. $$ f(n)=\frac{n^2+n}{2}=O(n^2) $$