# Showing $f(n)$ has upperbound of $O(g(n))$

I am currently enrolled in an algorithms course and was learning about upper, lower and tight bounds of functions.

I am confused on how to show that a function $f(n) = O(g(n))$ for some $n > n_0$ and $c$.

The definition for upper bound is: there exists positive constants $c$ and $n_0$ such that $0 \le f(n) \le c \cdot g(n)$ for all $n \ge n_0$.

I am currently stuck on a homework question similar to this:

$$T(n) = 25 n^5 \log(n) + 15n^5 + 8^5$$ Show that $T(n)$ has an upper bound of $O(n^5 \log(n))$

So this is what I have done so far:

$$0 \le 25n^5 \log(n) + 15n^5 + 8^5 \le c n^5 \log(n)$$

divide everything by $n^5$

$$0 \le 25\log(n) + 15 + 8^5/n^5 \le c\log(n)$$

Now I am stuck, how do I deal with $8^5/n^5$?

-
You can greatly improve the readability of your question by formatting formulas using $\TeX$. Check out: meta.math.stackexchange.com/q/5020/4583 – Ayman Hourieh Jan 27 '13 at 0:37

There is a more simple-minded approach.

Note that for $n\ge 3$, $15n^5\lt 15n^5\log n$. (Here I am assuming that by $\log$ you mean the natural logarithm. If it is the base $10$ logarithm, then $n$ has to be a bit larger.)

Note also that for $n\ge 8$, we have $8^5\lt n^5\log n$.

So if $n\gt 8$, your function is less than $41n^5\log n$. It follows that your function is $O(n^5\log n)$.

-

You have $$0\le 25\log n + 15 + \frac{8^5}{n^5}\le c\log n\;,$$

and you want to choose $c>0$ and $n_0$ so that this will be true for all $n\ge n_0$. First you could notice that if $n\ge 8$, then $\frac{8^5}{n^5}\le 1$, so for $n\ge 8$ we have

$$0\le 25\log n + 15 + \frac{8^5}{n^5}\le 25\log n+16\le c\log n\;,$$

provided that we can choose $c$ properly. Factor out the $25$: we’d like to get

$$25\left(\log n+\frac{16}{25}\right)\le c\log n\;.$$

Suppose that $n$ is big enough so that $\log n\ge\frac{16}{25}$; then

$$\log n+\frac{16}{25}\le 2\log n\;,\tag{1}$$

and therefore $$25\left(\log n+\frac{16}{25}\right)\le 50\log n\;,$$

so we can take $c=50$. How big does $n$ have to be for this to work? $\log n\ge\frac{16}{25}$ if and only if $n\ge e^{16/25}$, so taking $n\ge e$ will make $(1)$ true. We already required $n$ to be at least $8$, so we already know that $n\ge e$, and we can set $n_0=8$ and $c=50$.

-
Thanks for the long and clear answer, both you and Andre have the correct answer but Andre posted first so I am accepting his answer – stackErr Jan 27 '13 at 0:59
@user1160022: You’re welcome. His is probably more useful in the long run, since it shows you a better way to attack the problem; I decided to show you how to continue the attack that you’d chosen instead. – Brian M. Scott Jan 27 '13 at 1:02