$\begingroup$

I am working on this problem to find a function $f(N)$ s.t.

$$ f(N) \sim \sum_{k \geq 0}\frac{k!}{N^k} $$

where $\sim$ means that given functions $f$ and $g$, we have $f \sim g \implies f = O(g) \text{ and } f=\Omega(g)$.

For instance, given the right hand side of the equation above, on input $N$ we have the following (it's a divergent series)

$$ f(N) \sim 1 + \frac{1}{N} + \frac{1}{2N^2} + \frac{1}{6N^3} + O\bigg(\frac{1}{N^4}\bigg) $$

The closest function I can think of are the binomials where:

$$ (N \text{ choose } r) \sim \frac{N^r}{r!} $$

But it doesnt really equal the first equation above. Any help?

Answers