2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ There are $n^2$ of $n^2$, so it should add up to $n^4$ instead of $n^3$. $\endgroup$ – symmetricuser Oct 2 '14 at 7:01
  • $\begingroup$ 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... $\endgroup$ – Jonny Henly Oct 2 '14 at 7:03
  • 1
    $\begingroup$ 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$. $\endgroup$ – symmetricuser Oct 2 '14 at 7:04
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Ahhh yes, ye old closed form, I should have glanced at my closed form cheat sheet. $\endgroup$ – Jonny Henly Oct 2 '14 at 7:05
  • $\begingroup$ 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$. $\endgroup$ – symmetricuser Oct 2 '14 at 7:07
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ why are there $n^2$ such terms and not $n$ such terms? $\endgroup$ – Jonny Henly Oct 2 '14 at 7:01
  • $\begingroup$ 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$? $\endgroup$ – taninamdar Oct 2 '14 at 7:05
  • $\begingroup$ ohh. I like the $1$ to $10^2$ example, it's different when you bring actual numbers into it $\endgroup$ – Jonny Henly Oct 2 '14 at 7:07
  • $\begingroup$ @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$. $\endgroup$ – taninamdar Oct 2 '14 at 7:09
  • $\begingroup$ @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 ? $\endgroup$ – chouaib Oct 2 '14 at 7:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.