1

What is is the largest $0<c<4$ that satisfies $$2^{n + \sqrt{n}} \in O((4-c)^n)$$ ?

Elliot Gorokhovsky
  • 2,107
  • Are you looking for the minimum $c>0$ for which this stops being true? (also, your inclusion is strange. It should be either $\in$ or, with a slight abuse of notation, $=$.) – Clement C. Nov 25 '16 at 20:18
  • @ClementC. Ya I had the left side defined asymptotically originally, hence the subset notation, but then I edited and forgot to change it to \in. – Elliot Gorokhovsky Nov 25 '16 at 22:22

1 Answers1

2

For any fixed $c\in(-\infty, 4)$, we have $$ \frac{2^{n+\sqrt{n}}}{(4-c)^n} = 2^{n+\sqrt{n} - n\log_2 (4-c)} = 2^{(1-\log_2 (4-c))n + \sqrt{n}} \xrightarrow[n\to\infty]{} \begin{cases} \infty & \text{ if } 1-\log_2 (4-c) \geq 0 \\ 0 & \text{ if } 1-\log_2 (4-c) < 0 \\ \end{cases} $$ so for your satement to hold, you need (and it is sufficient) $1-\log_2 (4-c) < 0$, or equivalently $c < 2$.

Clement C.
  • 67,323