# Tagged Questions

23 views

### If $(en/k)^k e^{-(n-k)/2^k} < 1$, then $n \leq k^2 2^k (\ln 2) (1 + o(1))$.

Some technical details are omitted from an example in Alon and Spencer's The Probabilistic Method. The hypothesis of a theorem requires $$\binom{n}{k}(1 - 2^{-k})^{n-k} < 1.$$ The parameter $n$ ...
44 views

### Find real-valued sequences $x(n)$ for which $c^{x(n)} = o(1/n )$

For which $x=x(n)$ does it hold that $$c^x = o\left(\frac{1}{n}\right)$$ where $c\in(0,1)$ is a constant. So clearly, for $x=n$, this is true. But for which $x =o(n)$ does this hold? I thought ...
86 views

### Since $2^n = O(2^{n-1})$, does the transitivity of $O$ imply $2^n=O(1)$?

Let us assume that $f(n)=2^{n+1}$, $g(n)=2^n$ be two functions. Now, use limit to find $O(f(n))$: $\lim_{n\to\infty} \dfrac{2^{n+1}}{2^n}=2$. This is not equal to infinity, so the limit exists, hence ...
32 views

### Approximations for finite n in limit-based definition of the exponential function

The exponential function can be defined via: $$e^x = \lim_{n \rightarrow \infty} \left( 1 + \frac{x}{n} \right)^{n} = \lim_{n \rightarrow \infty} g(x; n)$$ In my problem, I actually have the right ...
92 views

### Please give me an example of the algorithm where $\Theta$ will be equal to $e^n$

Please give me an example of the algorithm where $\Theta$ or $O$ will be equal exactly to $e^n$ . The algorithm should not be simple counting from 0 till $e^n$ . It should be a clear relation of two ...
45 views

### Rate of convergence of an exponential function

If I have a function $$f = \exp(\sqrt{n} \cdot \frac{\sqrt{\log{n}}}{\sqrt{n}-\sqrt{\log n}}),$$ I can notice, that $$\lim_{n \to \infty} f = \infty,$$ but also I can notice that it goes very slowly ...
70 views

### Applications of the Exponential Integral?

this is my first time asking a question on here so please forgive me if I have made any formatting mistakes. I have the integral $f(x) = \int_0^\infty \frac{e^{-t}}{x + t} \; dt$ and I have shown the ...
59 views

### Which series of numbers effectively translates the factorial to the exponential function?

We have the relation of the Bernoulli numbers $$B_{2n} = (-1)^{n+1}\frac {2(2n)!} {(2\pi)^{2n}} \left(1+\frac{1}{2^{2n}}+\frac{1}{3^{2n}}+\cdots\;\right).$$ For $n>1$, the right hand sum ...
187 views

### Proving functions to be Big Oh

How do I determine if there exists a function $f$, such that $$f(n) = {\mathcal O}(\log n),$$ but $$2^{f(n)} ≠ {\mathcal O}(n).$$ Is ...
77 views

### Why is $3^n$ not in $\Theta(2^n)$

How is it that $3^n$ not in $\Theta(2^n)$, while $log_3 n$ is in $\Theta(log_2 n)$ ?
32 views

410 views

### Rate of growth of exponential functions

I have difficulties about proving the following: Prove that exponential functions $a^n$ have different orders of growth for different values of base $a>0$. It looks obvious that when $a=3$ it ...
### Rate of convergence of $\left[1+\frac{a}{x}\right]^x$ to $\operatorname{exp}[a]$ as $x\rightarrow\infty$
It's well-known that $\lim_{x\rightarrow\infty}\left[1+\frac{a}{x}\right]^x=\operatorname{exp}[a]$. I am wondering how fast does the limit converge as $x$ increases, and how the speed of convergence ...