# Average time complexity of simple recursive algorithm

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.

• An interesting exercise. What is the source? – vonbrand Jun 20 at 18:02
• It's from our Algorithms and Data Structures' first year course. – weno Jun 20 at 20:15

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

• Thank you for posting this. This is a little bit out of my knowledge, though. I know differential equations, but we were not introduced to them at all during our Algorithms classes. I will be definitely coming back here to understand this as soon as I can. – weno Jun 20 at 20:10