is $2^n = \Omega(2^{n + k})$ for some constant $k$?

39 Views Asked by At

From the definition of $\Omega$ notation, this would imply that $2^n \ge c 2^{n + k}$. Taking the $\log_2$ of both sides and simplifying, I see that $n \ge (n + k)\log_2(c)$. If I pick $c = 1, n_0 = 1,$ and $k$ to be some negative constant, then I can see this is true. I am wondering if this is a correct analysis, and that if I pick a positive $k$, then it is false. Thanks for your help.

1

There are 1 best solutions below

0
On BEST ANSWER

Formalizing the hints of the comments into a full answer:

If $2^n = \Omega(2^{n + k})$ then $2^{n + k}=O(2^n)$, meaning:

$$ \lim_{n \to \infty} \frac{2^{n+k}}{2^n}=c $$

For some finite or zero constant $c$.

$$ =\lim_{n \to \infty} 2^k=2^k=c. $$

$c$ is a finite or zero constant for all finite $k$.