How can I prove this big O problem without using the limit rule?

Question

I am ask to solve the following without using the limit rule.

$\dfrac{an^k}{\log_3n} \in O(n^k)$ but $\dfrac{an^k}{\log_3n} \not \in \Theta(n^k)$ knowing that $a\in\mathbb N$ and $a > 1$

This is what I tired to do: First I've establish that $ g(n) = \dfrac{an^k}{\log_3n}$ and that $ f(n) = n^k$

Then I demonstrate $g(n) \leq c \cdot f(n)$. I state that $\dfrac{1}{\log_3n}$ seems to be decreasing to 0 ( but isn't this using the limit rule?) I would pick $c = a$ therefore we would get the above inequality is true.

The problem is that I think I'm using the limit rule or simply just being implicit with limits.
I have not proven that this above indeed decrease.

I just tried it to experimentally with different values. With the second part how should I go about solving it?

Answer 1

To show the upper bound you just need to note $f(n)/n^k \le 1$ for $n \ge 3$.

For the lower bound, show that no matter what $c>0$ you choose, we have $1/\log_3 n < c$ for infinitely many $n$.