# Big Theta Expression Question

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!

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

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.

-
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