Solve the operations needed for the recursive formula

Question

$f(n) = 1+\frac{1}{n}\sum_{i = 0}^{n - 1} f(i)$

Base case: $f(0) = 0$

how can I solve the recurrence?

Answer 1

Your first step if you don't know what to do should be to find some of the small values of $f(n)$. This gives you $f(1) = 1$, $f(2) = \frac32 = 1 + \frac12$, $f(3) = \frac{11}{6} = 1 + \frac12 + \frac13$, and we begin to conjecture that $f(n)$ is the $n^{\text{th}}$ harmonic number $H_n := 1 + \frac12 + \frac13 + \dots + \frac1n$. If this is true, then it solves the problem, since $H_n$ is known to be approximately $\ln n + \gamma + O(\frac1n)$, where $\gamma$ is a constant, and in particular $H_n = O(\log n)$.

We can prove that $f(n) = H_n$ by induction. Assuming that the pattern holds for $f(1), f(2), \dots, f(n-1)$, we have $$ f(n) = 1 + \frac1n \sum_{i=1}^{n-1} H_i = 1 + \frac1n \sum_{i=1}^{n-1} \sum_{j=1}^i \frac1j. $$ If we switch the order of summation (which is always a good step to take when dealing with a double sum, we get $$ f(n) = 1 + \frac1n \sum_{i=1}^{n-1} H_i = 1 + \frac1n \sum_{j=1}^{n-1} \sum_{i=j}^{n-1} \frac1j = 1 + \frac1n \sum_{j=1}^{n-1} \frac{n-j}{j} = 1 + \frac1n \sum_{j=1}^{n-1} \frac nj - \frac1n \sum_{j=1}^{n-1}1 $$ and this simplifies to $1 + H_{n-1} - \frac{n-1}{n} = \frac1n + H_{n-1} = H_n$.

The summation at work, which is $$ \sum_{i=0}^{n-1} H_i = n H_n - n, $$ might be worth remembering and easy to remember, since it is very similar to the integral $$ \int_0^x \ln t \,\text{d}t = x \ln x - x. $$ It comes up in many other algorithm analyses (for instance, the expected running time of quicksort with a random pivot).

---

Alternative solution: seeing the recurrence $f(n) = 1 + \frac1n \sum_{i=0}^{n-1} f(i)$, we see a sum that's hard to evaluate but looks very similar from term to term. We can try to get a simpler recurrence by combining the recurrences for $f(n)$ and for $f(n-1)$ to eliminate the sum.

Take the equations $$n f(n) = n + \sum_{i=0}^{n-1}f(i)$$ and $$(n-1) f(n-1) = (n-1) + \sum_{i=0}^{n-2} f(i)$$ which are the recurrence relations for $n$ and for $n-1$, with denominators cleared to make the sums more similar. If we take the difference, we get $$n f(n) - (n-1) f(n-1) = 1 + f(n-1)$$ which simplifies to $n f(n) = 1 + n f(n-1)$, or $f(n) = f(n-1) + \frac1n$. Since $f(0) = 0$, we conclude that $$f(n) = \sum_{i=1}^n \frac1i = H_n.$$

Answer 2

Given any set $S$ of distinct natural numbers with cardinality $n$, pick $x \in S$. For any $y \neq x$ in $S$, $P(y > x) = \frac{1}{2}$ (naive definition of probability applies here). Thus, for the whole set, we expect $n \times \frac{1}{2}$ elements to be greater than $x$ by linearity of expectation. This gives that during each iteration, the size of the set is expected to halve. Thus, the set becomes empty after $\mathrm{log}_2 \> n$.