Showing that $4n + 3n \log_2n$ is $O(n\log_2n)$

Question

I need to prove that: $$ 4n+3n\log_2n \text{ is } O(n\log_2n) $$

How can I find $c$ and $n_0$ for $3n\log_2n$?

Also, using the big-Oh definition, I need to show that:

If $g_1(n)$ is $O(f(n))$ and $g_2(n)$ is $O(f(n))$, then the sum $g_1(n)+g_2(n)$ is $O(f(n))$.

Answer 1

I would start with the second question, and then seperatey prove that the two addends in the first function are $O(n\log_2 n)$.

As mentioned in a comment, to prove the second part you basically just have to write out what you know and what you need.

That $g_1(n)$ is $O(f(n))$ means that there exists constants $c_1$ and $n_1$ such that $g_1(n) \leq c_1f(n)$ for $n>n_1$.

That $g_2(n)$ is $O(f(n))$ means that there exists constants $c_2$ and $n_2$ such that $g_2(n) \leq c_2f(n)$ for $n>n_2$.

You need to find constants $c$ and $n_0$ such that $g_1(n)+g_2(n) \leq cf(n)$ for $n>n_0$. It should be easy to see constants that will work (note: they just have to work, not be optimal in any way).

For the first part, it should be really easy to see that $3n\log_2 n$ is $O(n\log_2 n)$, and that $4n$ is ain't much harder (this is where you'll need an $n_0$ that is larger than $1$).

Answer 2

For (2) it's enough to show that $g_1 + g_2 <2 \max \{g_1, g_2 \}$, which is clearly in $O(f(n))$.

For (1) obviously $4n < 4 n \log n $ for $n \geq 3$, hence the LHS is less than $8n \log n $ which is $O(n \log n$) by the definition.

Answer 3

Hint: calculate $\lim\limits_{n \to \infty} \frac{4n+4n \log{n}}{n \log{n}}$, the result is obviously 4.