Average time complexity of simple recursive algorithm

Work through the case in which m is fixed. If $n = 0$ there is just one print, if $n > 0$ you see there are $2 n$ calls to F2(m) and $n + 1$ calls to print. But $m$ isn't fixed, you have to average over it's possible values ($0 \le m \le n - 1$).

Call $T_n$ the number of times (on average) that print is called for $n$. Then:

$\begin{align*} T_n = \begin{cases} 1 & n = 0 \\ n + 1 + \frac{2}{n} \sum_{0 \le m \le n - 1} T_m & n > 0 \end{cases} \end{align*}$

Not exactly bog-standard...

Dig in with generating functions: Define $g(z) = \sum_{n \ge 0} T_n z^n$, multiply the $n > 0$ branch by $n z^n$ and sum over $n \ge 1$. Then identify some sums:

$\begin{align*} \sum_{n \ge 1} n T_n z^n &= \sum_{n \ge 1} n (n + 1) z^n + 2 \sum_{n \ge 1} z^n \sum_{0 \le m \le n - 1} T_m \\ \sum_{n \ge 0} n T_n z^n &= \sum_{n \ge 0} n (n + 1) z^n + 2 z \sum_{n \ge 0} z^n \sum_{0 \le m \le n} T_m \\ z g'(z) &= z \frac{d^2}{d z^2} \sum_{n \ge 0} z^n + 2 z \frac{g(z)}{1 - z} \\ z g'(z) &= z \frac{2}{(1 - z)^3} + 2 z \frac{g(z)}{1 - z} \\ \end{align*}$

Here we added some terms that are zero for symmetry, and adjusted indices in the last sum. Now solve the differential equation. We know $g(0) = T_0 = 1$:

$\begin{align*} g(z) &= \frac{c - 2 \ln(1 - z)}{(1 - z)^2} \\ &= \frac{1 - 2 \ln(1 - z)}{(1 - z)^2} \end{align*}$

We want the coefficient of $z^n$:

$\begin{align*} T_n &= [z^n] g(z) \\ &= 2 (-1)^n \binom{-2}{n} - [z^n] \frac{\ln(1 - z)}{(1 - z)^2} \\ &= 2 \binom{n + 2 - 1}{2 - 1} - [z^n] \frac{\ln(1 - z)}{(1 - z)^2} \\ &= 2 \frac{n + 1}{1} - [z^n] \frac{\ln(1 - z)}{(1 - z)^2} \\ &= 2 n + 2 - 2 [z^n] \frac{\ln(1 - z)}{(1 - z)^2} \end{align*}$

The last term is somewhat troublesome. But we know that $\frac{A(z)}{1 - z}$ is the generating function of partial sums, doing it twice here:

$\begin{align*} [z^n] \frac{- \ln(1 - z)}{(1 - z)^2} &= \sum_{0 \le k \le n} \sum_{1 \le j \le k} \frac{1}{j} \\ &= \sum_{1 \le k \le n} \frac{n - k + 1}{k} \\ &= (n + 1) H_n - n \end{align*}$

We use harmonic numbers $H_n = \sum_{1 \le k \le n} \frac{1}{k}$ here.

Pulling all together:

$\begin{align*} T_n &= 2 n + 2 + 2 (n + 1) H_n - 2 n \\ &= (n + 1) H_n + 2 \end{align*}$