Which is the best way to find the complexity?

Question

I want to find the asymptotic complexity of the function:

$$g(n)=n^6-9n^5 \log^2 n-16-5n^3$$

That's what I have tried:

$$n^6-9n^5 \log^2 n-16-5n^3 \geq n^6-9n^5 \sqrt{n}-16n^5 \sqrt{n}-5 n^5 \sqrt{n}=n^6-30n^5 \sqrt{n}=n^6-30n^{\frac{11}{2}} \geq c_1n^6 \Rightarrow (1-c_1)n^6 \geq 30n^{\frac{11}{2}} $$

We pick $c_1=2$ and $n_1=3600$.

$$n^6-9n^5 \log^2 n-16-5n^3 \leq n^6, \forall n \geq 1$$

We pick $c_2=1, n_2=1$

Therefore, for $n_0=\max \{ 3600, 1 \}=3600, c_1=2$ and $c_2=1$, we have that:

$$g(n)=\Theta(n^6)$$

Could you tell me if it is right? $$$$

Also, can I begin, finding the inequalities or do I have to say firstly that we are looking for $c_1, c_2 \in \mathbb{R}^+$ and $n_0 \geq 0$, such that:

$$c_1 f(n) \leq g(n) \leq c_2 f(n), \forall n \geq n_0$$

and then, after having found $f(n)$, should I say that we are looking for $c_1, c_2 \in \mathbb{R}^+$ and $n_0 \geq 0$, such that:

$$c_1 n^6 \leq g(n) \leq c_2 n^6, \forall n \geq n_0$$

Answer 1

there's a faster way: if

$$ \lim_{x\to \infty}\frac{f(x)}{g(x)}\in\mathbb{R}/\{0\} $$ then

$$ f(n)=\Theta(g(n)) $$

And this is easy to prove

Answer 2

For a log-polynomial expression $\sum a_kn^{i_k}\log^{j_k}(n)$, take the highest power of $n$ and in case of equality take the highest power of the $\log$.

In your case, the dominant term is $n^6$, and $$\frac{g(n)}{n^6}=1-\frac{9\log^2 n}n-\frac{16}{n^5}-\frac5{n^3}.$$ The limit is clearly $1$.

Also note that the second term has a maximum for $n=e^2$ so that the ratio increases for higher values.

Taking $n\ge1000$ to get a positive constant, $$0.57n^6<g(n)<n^6.$$