Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
1  
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
add comment

2 Answers 2

up vote 0 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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