3
votes
1answer
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$ ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
4
votes
1answer
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 ...
3
votes
0answers
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 ...
0
votes
1answer
187 views

Proving functions to be Big Oh

How do I determine if there exists a function $f$, such that \begin{equation} f(n) = {\mathcal O}(\log n), \end{equation} but \begin{equation} 2^{f(n)} ≠ {\mathcal O}(n). \end{equation} Is ...
3
votes
2answers
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)$ ?
0
votes
2answers
32 views

limit with exponential

I am trying to solve asymptotic relation between 2 functions: $$f(n)=2^n*n$$ $$g(n)=\frac {3^n}{n^2} $$ I started to solve $$\lim_{x\to \infty} \frac{2^n*n^3}{3^n}=\lim_{x\to \infty} (\frac ...
1
vote
1answer
69 views

Is there an “interesting” function that grows faster than $n^{kn}$ but slower than $2^{2^n}$ — relates to understanding googolplex

Motivation: I'm looking for some sort of convenient fact I can use to grasp the size of a googolplex. For a googol we observe a convenient one; it's very nearly equal to 70!. But for a googolplex I ...
1
vote
0answers
62 views

How to analyze the asymptotic properties of this function?

Let the function $$f(\mathbf{r})=\int_{\Omega }e^{i\mathbf{k} \cdot \mathbf{r}}d^2\mathbf{k}$$, where $\mathbf{k} ,\mathbf{r}\in\mathbb{R}^2$, and $\Omega \subset \mathbb{R}^2$ is some finite region ...
1
vote
1answer
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 ...
2
votes
1answer
162 views

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 ...
3
votes
1answer
368 views

Comparing the asymptotic growth of two exponential functions

I'd like to compare the asymptotic growth rates of two functions: Cayley's formula for the number of trees on $n$ vertices: $n^{n-2}$ The number of possible graphs on $n$ vertices: $2^{n \choose 2} ...
3
votes
1answer
240 views

“Proof” that if f(x) ~x, e^f(x) ~ e^x

While it is not true that $f(x)\sim x \implies e^{f(x)}\sim e^x,$ I can't spot the error in this "proof" by induction--or at least I can't articulate it well. Let $f(x)\sim x$ and $x > 1$ P(1): ...
-1
votes
1answer
175 views

How to find asymptotic entire functions?

I want to know how to find analytic functions $f(z)$ that are asymptotic and analytic on and near the real line of functions of the type $\ln(C +\exp(P(z^2)))$ where $C$ is a complex constant and $P$ ...
3
votes
6answers
525 views

Proof by contradiction that $n!$ is not $O(2^n)$

I am having issues with this proof: Prove by contradiction that $n! \ne O(2^n)$. From what I understand, we are supposed to use a previous proof (which successfully proved that $2^n = O(n!)$) to find ...