A proof I am reading makes the following claim:
Let $D,n$ be positive integer parameters. If $D<2^{o(\sqrt{\log n})}$, then $D^{\lceil{\sqrt{\log n}} \rceil} \leq n$.
Why should this be?? My attempt at understanding it:
We have $D=2^{f(n)}$, for some $\frac{f(n)}{\sqrt{\log n}} \rightarrow 0$ as $n\rightarrow \infty$. So, we also have $\frac{f(n)}{\sqrt{\log n} -1} \rightarrow 0$.
So, $D^{\lceil{\sqrt{\log n}} \rceil} =2^{f(n)\lceil{\sqrt{\log n}} \rceil}\leq 2^{f(n)\cdot ({\sqrt{\log n}} +1)}=2^{\frac{f(n)}{\sqrt{\log n} -1} {((\log n)-1)} } \leq 2^{\frac{f(n)}{\sqrt{\log n} -1} {\log n} }=n^{\frac{f(n)}{\sqrt{\log n} -1}}$ .
But then I don't see how to bound this above by $n$. If I want $n^{\frac{f(n)}{\sqrt{\log n} -1}}\leq n$, then I need ${\frac{f(n)}{\sqrt{\log n} -1}}\leq 1$. But all I can say is that the LHS tends to $0$, rather than is always $\leq 1$. So it seems I am stuck... unless I have misinterpreted the meaning of the author?
CONTEXT: https://www.cs.bgu.ac.il/~elkinm/book.pdf I am referring to the paragraph before Lemma 10.6 on pg113, and the last paragraph of the proof of Lemma 10.6, on pg114.
We prove this claim for all real $D,n\ge 1$. By defining $x=e^{u^2}$ with $u>0$, we must prove that$$D<2^{o(u)}\implies D^{\lceil u\rceil}<e^{u^2}$$Note that $$D<2^{o(u)}\implies D^{\lceil u\rceil}<2^{\lceil u\rceil\cdot o(u)}<2^{(u+1)o(u)}=2^{u\cdot o(u)}=e^{u\cdot o(u)}<e^{u^2}$$where the equalities and the last inequality hold true hence the definition of Little-O Notation.