I'm currently taking a Discrete Mathematics course which just started the chapter on The Growth of Functions. A (very) brief overview was given in lecture that covered the Big-O definition.
Let $f$ and $g$ be functions from the set of integers or the set of real numbers to the set of real numbers. We say that $f(x)$ is $O(g(x))$ if there are constants $C$ and $k$ such that $$|f(x)| \le C|g(x)|$$ whenever $x \gt k$ . $[$This is read as "$f(x)$ is big-oh of $g(x)$."$]$
And that is where the lecture left off. Then in the online homework tonight I was given the following problem.
Find the best Big-O function for the function $f(n)=1+2+3+ \ldots +(n^2-1)+n^2$
Note: This chapter in the book is five pages long and covers Big-O Notation, The Growth of Combinations of Functions, and Big-Omega and Big-Theta Notation. There are four examples on those three subjects and 75 exercises with no listed answers (so they're fun to gaze at hopelessly). I searched the Google and looked at the Big Omega posts on the StackExchange sites but I was pressed for time and couldn't find what I was looking for. Anyway I'm not the best at this and I tried but can't seem to get it, so here it goes...
Using the definition
$$1+2+3+\ldots+(n^2-1)+n^2 \le n^2+n^2+\ldots+n^2$$ and since the number of summations of $n^2$ is equal to $n$ it would give you $n(n^2)$ which would be $n^3$? Thus making the following inequality correct $$1+2+3+\ldots+(n^2-1)+n^2 \le n^2+n^2+\ldots+n^2=n^3$$
and finally $$f(n)=1+2+3+\ldots+(n^2-1)+n^2 \;\;\text{is}\;\; O(n^3)$$
which came back as being incorrect. The answer turned out to be $n^4$ which I cannot figure out and I was hoping someone could shed some light?
We can actually get a closed form for $f(n)$: $$\sum_{i=1}^{n^2} i = \frac{n^2(n^2+1)}{2} = \frac{n^4}{2} + \frac{n^2}{2}.$$
It is easy to see, from here, that $f(n) = O(n^4)$.