Prove that $\log_2 n$ is not bounded polynomially from below, need 2nd step

Question

i.e. that $\log_2 n\not\in\Theta(n^x)$ for any $x > 0$

i shall not use induction on $x$ ( as $x = 1$ base case etc)

my guess is : i use the def. of big theta:

$$ 0≤c_1·n^x \le \log_2 n \le c_2· n^x $$

where do i go from here?

Answer 1

ok, this is simple actually, prove by contradiction:

assume it is true, then big-theta means it is in between c1 * $n^x$ and c2 * $n^x$.

in other words, if we take limit of f(n) / g(n) -must be nonzero, finite( non infinite) and must exist

take limit:

lim (lgn / $n^x$) as n -> inf. = lg(inf) / $n^(inf)$ = inf.

which is a contradiction. done!