0
$\begingroup$

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.

enter image description here

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.

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

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – weno Jun 20 at 20:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.