Prove $8n^{3}$ $+$ $√n$ $∈$ $Θ$($n^{3})$

Question

just wondering if I proved this question correctly. Any hints, help, or comments would be appreciated.

There are two cases to consider to prove $8n^{3}$ $+$ $√n$ $ϵ$ $Θ(n^{3})$

1. $8n^{3}$ $+$ $√n$ $ϵ$ $O$$(n^{3})$
2. $8n^{3}$ $+$ $√n$ $ϵ$ $Ω$$(n^{3})$

1.)

There should exist a constant $c > 0$ and $k$ where $8n^{3}+ √n < cn^{3}$ for every $n > k$.

In this case consider $c = 9$, then there must exist a case where $8n^{3}+ √n < 9n^{3}$ holds true.

Therefore, when $k = 1$ then $8n^{3}$ $+$ $√n$ $ϵ$ $O$$(n^{3})$ because the inequality $8n^{3}+ √n < 9n^{3}$ will be true in every case of $n > k$.

2.)

There should exist a constant $d > 0$ and $j$ where $8n^{3}+ √n > dn^{3}$ for every $n > j$.

In this case consider $d = 8$, then there must exist a case where $8n^{3}+ √n > 8n^{3}$ holds true.

Therefore, when $j = 0$ then $8n^{3}$ $+$ $√n$ $ϵ$ $Ω$$(n^{3})$ because the inequality $8n^{3} + √n > 8n^{3}$ will be true in every case of $n > j$

Answer 1

Your proof is correct, however all you have to observe is that the degree of the LHS equals the degree of the RHS. :)

Answer 2

An alternative is to use the limit test. Consider $f(n) = 8n^{3} + \sqrt{n}$ and:

$$L = lim_{n \to \infty} \frac{f(n)}{n^{3}}$$

Note $f(n) \in o(n^{3})$ iff $L = 0$ (and little-o is the strict inequality, which implies Big-O).

Similarly, $0 < L < \infty \implies f(n) \in \Theta(n^{3})$.

And finally, $L = \infty \implies f(n) \in \omega(n^{3}) \implies f(n) \in \Omega(n^{3})$. Little-omega is also the strict inequality of Big-Omega.

I think this is easier, but your proof is valid.