How can I prove that $g(n) \not \in \Theta (f(n))$?

Question

I have :

$f(n) = n^k$ with k an integer

$g(n) = \dfrac{a}{log_3 n}$ with $a$ a natural > 1

How do I go about disproving this: $c_1 f(n) \leq g(n) \leq c_2 f(n)$?

Not allowed to use limits.

Answer 1

You should know that $f(n)$ is much greater than $g(n)$ for $k \ge 0$, so that is the side of the inequality that will fail. In this case $g(n) \to 0$ because the log increases without bound, while $f(n)$ is at least $1$. On the other hand, if $k \lt 0, f(n) \lt g(n)$ and the other side fails because the log grows much more slowly than any polynomial.

Answer 2

Suppose first that $k > 1$. If we had a $c > 0$ and an $n_0$ such that $$c n^k \leq \dfrac{a}{log_3 n},$$ then, since logarithm functions are increasing, we would have that

$$\log_3 c + k \log_3 n \leq \log_3 a - \log \log_3 n$$

We can assume wlog that $c < 1$. But then

$$(\log_3 c - \log_3 a) + \log_3 \log_3 n \leq - k \log_3 n$$

Since $\log \log_3 n$ is positive and $- k \log_3 n$ is negative for $n \geq 3$, this cannot hold as soon as $n_0 \geq 3^{(3^{(\log_3 a - \log_3 c)})}$.

Now suppose $k \leq -1$. If we had a $c > 0$ and an $n_0$ such that $$\dfrac{a}{log_3 n} \leq c n^k$$ then, since logarithm functions are increasing, we can use the same line of reasoning as in the above.