Prove $an\log(n)+3n = \Theta(n\log(n))$

Question

Using the asymptotic definition of $\Theta(.)$ I need to show that:

$$an\log(n)+3n = \Theta(n\log(n))$$

for some $a$, fixed constant.

My attempt

In order to prove what's above, I need to find a suitable positive $c_1$ and $n_0$ values such that as $\forall n \geq n_0$, then $an\log(n)+3n \leq c_1(n\log(n))$. (And then repeat the same process to show that $\exists c_2 > 0, n_0$ so that $c_2(n\log(n))\leq an\log(n)+3n\;(\forall n>n_0))$.

Since I don't know which value $a$ might take on, I've thought to reason by cases: $a > 0$, $a = 0$, $a \leq 0$.

Let's assume $a > 0$, then let $c_1 = 4a$, $n_0 = 2$: $$an\log(n)+3n \leq 4an\log(n)$$ $$a2\log(2)+3 \leq 8a\log(2)$$ we can see how $\forall n \geq 2$ that inequality still holds.

Let's now assume $a = 0$, then let $c_1 = 4a$, $n_0 = 2$: $$4n \leq 4n\log(n)$$

Lastly let's assume $a < 0$, then let $c_1 = 4$ and $n_0 = 1$:

$$an\log(n)+3n \leq 4n \log(n)$$

then it is trivial because the left side of the inequality is always going to be negative and therefore smaller than the right side which is a positive quantity.

And that shows that $an\log(n)+3n = O(n\log(n))$. Is my reasoning sound? Have I made any mistakes? Any feedback is highly appreciated.

Answer 1

Well, if $a=0$ I don't think the claim is true. Apart from that, I think it looks right, although you've only showed one direction of the required inequalities (the other direction will fail for $a=0$).

However, there should be an easier way. Take $f(n)=an\log n + 3n$, $g(n)=n \log n$ and $h(n)=f(n)/g(n)$. It is easy to show that $h(n) \to a$ as $n \to \infty$. What does this tell you? Well it means that $|(an \log n +3n)/(n \log n) -a|$ is bounded for $n$ large enough. Require for example that $|(an \log n +3n)/(n \log n) -a|<s$, for some $s$ whenever $N>n_0$, for some $n_0$, whose existence is guaranteed by the limit. This implies that $|(an \log n +3n)/(n \log n)|<\mathrm{max}(|s-a|, |s+a|)$.

If now $a \neq 0$, you can look at the limit of $1/h(n)$ (that is $1/a$) and repeat the argument.

You only have to show the existence of your $c_1$ and $n_0$, not necessarily find their values.

EDIT: I reckoned my answer required some elaboration.