Big Theta Expression Question

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!

Answer 1

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.