Big-O notation of $n^2/2+n/2$

Question

I'm just starting to use big-O notation and I just wanted to make sure I was on the right track. My algorithm is the following:

$$\frac12n^2+\frac12n$$

I came up with $O(n^2)$ is that correct?

Answer 1

It is the case that $$\frac{n^2 + n}{2} \leq 1\cdot n^2$$ as long as $n \geq 2$. So the answer is yes. Just remember that at the same time it's also of $O(n^3)$ and $O(2^n)$, since big-O only gives an upper bound. However, as a general rule, we want to find the smallest simple expression that works, and in this case it's $n^2$.

Answer 2

You are right.

$$O\left({1\over 2} n + {1\over 2} n^2\right)= O\left \{ \max \left({1\over2} n,{1\over2} n^2\right) \right \}=O(n^2)$$