How to prove non-equivalence of this?
$a^n = \Omega(b^n)$
when
$0 < a < b$
How to prove non-equivalence of this?
$a^n = \Omega(b^n)$
when
$0 < a < b$
Suppose $a^n=\Omega(b^n)$ i.e. $a^n\ge c\cdot b^n$ for some $c>0$ and all $n>N$ for some $N$. Now $0 $\implies n\log(a/b)\to-\infty\implies\exp(*)=(a/b)^n\to0$ which implies for any $\epsilon>0$ there is an $M$ such that $n>M\implies(a/b)^n<\epsilon$. Specialize $\epsilon=c$ and set $k=\max\{N,M\}+1$ in which case $a^k\ge c\cdot b^k$ (by hypothesis) and $(a/b)^k