Smallest $s$ such that $\sum_i^n (1-\frac{1}{i})^s<\epsilon$ Take $f(n)$ defined as follows
$$\begin{array}{lll}
g(s,n)&=&\frac{1}{n}\sum_{i=1}^n \left(1-\frac{1}{i}\right)^s\\
f(n)&=&\text{smallest } s \text{ such that } g(s,n)<\epsilon
\end{array}$$
Empirically, $f(n)$ grows linearly in $n$, and in $-\log\epsilon$, is there a good way to see this analytically?


notebook
 A: First, suppose $s \ge n\log\dfrac{1}{\epsilon}$. Then since $1-\dfrac{1}{k} \le 1-\dfrac{1}{n}$ for $1 \le k \le n$, and $\left(1-\dfrac{1}{n}\right)^n \le \dfrac{1}{e}$ for all $n \ge 1$, we have
\begin{align*}
g(s,n) &= \dfrac{1}{n}\sum_{k = 1}^{n}\left(1-\dfrac{1}{k}\right)^s 
\\
&\le \dfrac{1}{n}\sum_{k = 1}^{n}\left(1-\dfrac{1}{n}\right)^s 
\\
&= \left(1-\dfrac{1}{n}\right)^s 
\\
&\le \left(1-\dfrac{1}{n}\right)^{n\log\tfrac{1}{\epsilon}}
\\
&\le e^{-\log\tfrac{1}{\epsilon}} 
\\
&= \epsilon.
\end{align*}
Now, suppose $n \ge 4$ and $s \le \dfrac{1}{2\ln 4}n\log\dfrac{1}{2\epsilon}$. Then since $1-\dfrac{1}{k} \ge 1-\dfrac{2}{n}$ for $\left\lceil\tfrac{n}{2}\right\rceil \le k \le n$, and $\left(1-\dfrac{2}{n}\right)^{n/2} \ge \dfrac{1}{4}$ for all $n \ge 4$, we have
\begin{align*}
g(s,n) &= \dfrac{1}{n}\sum_{k = 1}^{n}\left(1-\dfrac{1}{k}\right)^s 
\\
&\ge \dfrac{1}{n}\sum_{k = \left\lceil\tfrac{n}{2}\right\rceil}^{n}\left(1-\dfrac{1}{k}\right)^s 
\\
&\ge \dfrac{1}{n}\sum_{k = \left\lceil\tfrac{n}{2}\right\rceil}^{n}\left(1-\dfrac{2}{n}\right)^s 
\\
&\ge \dfrac{1}{n}\left(n-\left\lceil\tfrac{n}{2}\right\rceil+1\right)\left(1-\dfrac{2}{n}\right)^s 
\\
&\ge \dfrac{1}{2}\left(1-\dfrac{2}{n}\right)^s 
\\
&\ge \dfrac{1}{2}\left(1-\dfrac{2}{n}\right)^{\tfrac{1}{2\ln 4}n\log\tfrac{1}{2\epsilon}}
\\
&\ge \dfrac{1}{2}\cdot 4^{-\tfrac{1}{\ln 4}\log\tfrac{1}{2\epsilon}}
\\
&= \epsilon.
\end{align*}
This proves that $\dfrac{1}{2\ln 4}n\log\dfrac{1}{2\epsilon}+1 \le f(n,\epsilon) \le n\log\dfrac{1}{\epsilon}$ for $n \ge 4$. So $f(n,\epsilon)$ grows linearly in $n$ and linearly in $\log\dfrac{1}{\epsilon}$.
