Is there a difference between the method to find a big-O function and the method to find the best big-O function. Take for example the following function:
$f(n) = 1 + 2 + 3 + ... + n$
It is easy to show that $f(n)$ is $\mathcal{O}(n^2)$ like this:
$1 + 2 + 3 + ... + n \leq n + n + n + ... + n = n \cdot n = n^2$ for $n \geq 1$
Such that the witnesses are $C=1$ and $k=1$
But how do I know if this is the best big-O function? I need to know how to do this for more complex functions than the one shown.
We have $f(n)=\frac{n(n+1)}{2} \ge \frac{n^2}{2}$ and so $f$ is $\Omega(n^2)$.
Since $f$ is $O(n^2)$, we conclude that $f$ is $\Theta(n^2)$.
It is in this sense that $n^2$ is the "best" function for $f$, in the asymptotic sense, when constants do not matter.
On the other hand, $f(n) \sim \frac{n^2}{2}$, and so $\frac{n^2}{2}$ is also the best function for $f$, in the asymptotic sense, when constants matter.