# Big-O Function for f(x)

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?

• There are $n^2$ of $n^2$, so it should add up to $n^4$ instead of $n^3$. – symmetricuser Oct 2 '14 at 7:01
• but why are there $n^2$ of $n^2$ and not $n$ of $n^2$, is there an unwritten rule that if you see $\ldots(n^2-1)+n^2$ that it means your dealing with $n^2$ entries? Nothing jumps out and tells me that... – Jonny Henly Oct 2 '14 at 7:03
• On the left hand side of the inequality, you have $1 + 2 + \cdots + n^2$. That's $n^2$ numbers since you're counting from 1 up to $n^2$. – symmetricuser Oct 2 '14 at 7:04

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)$.

• Ahhh yes, ye old closed form, I should have glanced at my closed form cheat sheet. – Jonny Henly Oct 2 '14 at 7:05
• Hehe yes, $\sum_{i=1}^n i = n(n+1)/2$ is very useful and can be derived very easily! Just list the sum $1+2+\cdots+n$ and write down the sum in reverse order $n+(n-1)+\cdots+1$ right under it. The two terms that line up all add up to $n+1$, and there are $n$ of them. So the original sum is $n(n+1)/2$. – symmetricuser Oct 2 '14 at 7:07

In $1 + 2 + + \cdots + (n^2-1)+n^2$, each term is $\le n^2$, and there are $n^2$ such terms, therefore it is in $O(n^2\cdot n^2) = O(n^4)$.

• why are there $n^2$ such terms and not $n$ such terms? – Jonny Henly Oct 2 '14 at 7:01
• How many terms are there from $1$ to $n^2$? $n$ or $n^2$? Easier still, how many terms from $1$ to $10^2 = 100$, $10$ or $100$? – taninamdar Oct 2 '14 at 7:05
• ohh. I like the $1$ to $10^2$ example, it's different when you bring actual numbers into it – Jonny Henly Oct 2 '14 at 7:07
• @JonnyHenly It is kinda obvious that there are $k$ terms in $1$ to $k$. So, there are $n^2$ terms in $1$ to $n^2$. – taninamdar Oct 2 '14 at 7:09
• @JonnyHenly: your comment about how many terms confused me! I mean you didn't complain in the accepted answer's comments about the sum being from 1 to n square ? – chouaib Oct 2 '14 at 7:45