Average time complexity of simple recursive algorithm

Question

I need to calculate average time complexity of the following pseudocode. It's not a homework, I am preparing for an exam, and it's going quite poorly so far. So all kind of tips are welcomed.

I am not sure if I should define recursive relation that would look +- like that:

$$\begin{cases} T(0) = 1 \\ T(n) = b_{n}T(n-1) + c_{n}\end{cases}$$

and then solve it to get my time complexity, or just somehow calculate time complexity straight away.

Some initial ideas: propability $p_{1}$ that $n > 0$ is $\frac{1}{n}$, therefore propability that instruction in 13rd row will execute is $p_{2} = 1 – p_{1} = 1 – \frac{1}{n}$

and 10th's row instruction is executed $n$ times.

So perhaps average time complexity should approximately look like that?

$$T_{avg}(n) = \underbrace{\sum_{i = 1}^{n}\frac{1}{n}(n-1)}_{\text{instruction 10}} + \overbrace{\sum_{i = 1}^{n}(1 – \frac{1}{n})1}^{\text{instruction 13}}$$

and then of course calculate it futher? How close am I?

I am mostly confused about lines $6, 7$ that imply recursion and how to tie up everything together.

All tips are welcomed. Thanks.

Answer 1

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*}$