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 need help - I have to express this function: $f(n)=15n \log n + 12n + 9 \log n +25$ in terms of big theta notation. I believe that it is $\Theta(n \log n)$, but I have to prove it mathematically. My math is awful, so if you could explain step by step that would be fantastic!

share|improve this question
    
Take a look at this question and answer. –  Antonio Vargas Jan 28 '13 at 21:14

1 Answer 1

up vote 0 down vote accepted

We need to show that there exist constants $k_1$ and $k_2$ such that $$k_1 n\log n \le f(n) \le k_2 n\log n$$ whenever $n$ is sufficiently large.

It is clear that $15n\log n \le f(n)$. so we can take $k_1=15$.

Now we need to find a constant $k_2$ such that if $n$ is large enough, then $f(n)\le k_2 n\log n$.

We assume that $\log$ means logarithm to the base $e$, though what we will write will be correct also if the base is $2$. Very minor change is needed if base $10$ is meant.

Note that $12n \le 12 n\log n$ if $n\ge 3$.

Also, $9\log n \le n\log n$.

Finally, $25\le 25n\log n$ if $n\ge 25$. (Of course we don't need to go all the way to $25$.)

Thus $f(n)\le (15+12+9+25)n\log n$ if $n\ge 25$. So we can take $k_2=61$.

Remark: We do not need to exhibit explicit $k_1$ and $k_2$: showing that they exist is enough. But in this example, giving explicit $k_1$ and $k_2$ is not hard, so for the sake of concreteness we might as well do it.

share|improve this answer
    
This makes a bit of sense - though could you clarify this line for me? It is clear that 15nlogn≤f(n). so we can take k1=15. It's not so clear to me :) –  Yecats Jan 28 '13 at 22:57
    
Soon it will clear. $f(n)=15n\log n + \text{stuff}$ where the stuff is clearly positive. The stuff is in fact bigger than $25$ for all (positive) $n$. All I am saying is that $f(n)$ is bigger than the first term of %f(n)$. –  André Nicolas Jan 28 '13 at 23:30

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.