Prove the theorem

Question

Stuck on this problem for a day by now, please help.

Answer 1

Given $f(n) = 7n\sqrt{n} + 5n + 3 \sqrt{n} - 2$, we prove $f \in O(n\sqrt{n})$.

Recall that if $f_1 \in O(g_1)$ and $f_2 \in O(g_2)$, then

$$f_1+f_2 \in O\big(\max(g_1,g_2)\big)$$ and

$$f_1\cdot f_2 \in O\big(g_1 \cdot g_2)$$

So, in order to find big-O of $f(n)$, we must find big-O of each term and then take the maximum.

FIRST TERM:

$7n \in O(n)$ and $\sqrt{n} \in O(\sqrt{n})$, so $7n\sqrt{n} \in O(n \sqrt{n})$ by the second rule above.

SECOND TERM:

$5n \in O(n)$

THIRD TERM:

$3\sqrt{n} \in O(\sqrt{n})$

FOURTH TERM:

$-2 \in O (1)$

Now that we have found big-O of each term, we find the maximum: $\max(n \sqrt{n}, n, \sqrt{n}, 1)=n\sqrt{n}$

Hence, $7n\sqrt{n} + 5n + 3 \sqrt{n} - 2 \in O(n\sqrt{n})$

Answer 2

Step 1: look at the definition. You need to find $n_0$ and $c$, such that for any $n\ge n_0$ you have $$7n\sqrt n+5n+3\sqrt n-2\le cn\sqrt n$$ Since $n\gt 0$, just divide the entire inequality above by $n\sqrt n$. You get $$7+\frac 5{\sqrt n}+\frac 3n-\frac 2{n\sqrt n}\le c$$ You can ignore the negative term since $$7+\frac 5{\sqrt n}+\frac 3n-\frac 2{n\sqrt n}\le 7+\frac 5{\sqrt n}+\frac 3n$$ Note that except for $7$, the terms with $n$ are decreasing with increasing $n$. So just take $n_0=1$ and find a $c$ value.