Time complexity of simple recursive procedure with random variable

Question

Considering this function:

function F1(n);
begin
  if n > 0 then
    for i := 0 to n do
      print(i);
      print(n - i);
    end for
    m := random(0, n - 1);   // tricky part
    F1(m);
  else
    print(n);
  end if
end function

I need to compute average time complexity of $F1$ procedure. Dominant operations are print calls. $random(d, g)$ returns random integer value from range $d, \cdots, g$.

So far I got this relation:

$$\begin{cases}T(0) = 1 \\ T(n) = T(m) + 2(n+1) \end{cases}$$

I believe it is correct so far. But I need to get rid of the $T(m)$ thing and make it dependant on something like $\underbrace{T(n-1)}_{\text{well, that'd be worst case}}$ or $T(\frac{n}{2})$ etc.

I was thinking in order to get rid of $m$ parameter perhaps I need to compute some sum, like:

$$m = \sum_{i=0}^{n-1}\frac{i}{n} = \sum_{i=1}^{n}\frac{i}{n+1} = \frac{n}{2}$$

But I think the second sum is not really equivalent to the first sum, is it?

Regardless, my question is how to get rid of the $m$ parameter from my relation above.

Answer 1

This solution is slightly different:

Random always returns integer from $\{0,1, \cdots , n-2, n-1 \}$ interval. Probability is $\frac{1}{n}$ for each individual result.

$$\begin{cases}T(0) = 1 \\ T(n) = \frac{1}{n} \sum_{m=0}^{n-1} T(m) + 2n + 2 \end{cases}$$

---

$$T(n) = \frac{1}{n} \sum_{m=0}^{n-1}T(m) + 2n + 2 \quad \Bigg/\cdot n$$

$$\color{blue}{nT(n) = \sum_{m=0}^{n-1}T(m) + 2n^2 + 2n}$$

---

For $n = n -1$ we have:

$$(n-1)T(n-1) = \sum_{m=0}^{n-2}T(m) + 2(n-1)^2 + 2(n-1)$$

$$(n-1)T(n-1) = \sum_{m=0}^{n-2}T(m) + 2n^2 - 4n + 2 +2n - 2$$

$$\color{red}{(n-1)T(n-1) = \sum_{m=0}^{n-2}T(m) + 2n^2 - 2n}$$

---

Subtracting one from the another:

$$\color{blue}{nT(n)} - \color{red}{(n-1)T(n-1)} = \color{blue}{\sum_{m=0}^{n-1}T(m) + 2n^2 + 2n} - \Bigg(\color{red}{\sum_{m=0}^{n-2}T(m) + 2n^2 - 2n}\Bigg)$$

$$nT(n) - (n-1)T(n-1) = \sum_{m=0}^{n-1}T(m) - \sum_{m=0}^{n-2}T(m) + 4n$$

$$nT(n) - (n-1)T(n-1) = T(n-1) + 4n$$

$$nT(n) = (n-1)T(n-1) + T(n-1) + 4n$$

$$nT(n) = nT(n-1) + 4n$$

---

Hence the recurrence relation is of the form:

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

---

Which can be further solved for example by applying method of summation factors:

$$T(n) = \frac{1}{S_{n}a_{n}} \Bigg(T_{0}S_{1}b_{1} + \sum_{k=1}^{n}S_{k}c_{k}\Bigg)$$

$$S_{n} = \frac{a_{1}a_{2}\cdots a_{n-2}a_{n-1}}{b_{2}b_{3} \cdots b_{n-1}b_{n}} = \frac{\prod_{k=1}^{n-1}a_{k}}{\prod_{k=2}^{n}b_{k}} = \frac{\prod_{k=1}^{n-1}k}{\prod_{k=2}^{n}k} = \frac{(n-1)!}{n!} = \frac{(n-1)!}{(n-1)!n} = \frac{1}{n}$$

$$\Longrightarrow T(n) = \frac{1}{\frac{n}{n}}\Bigg(1 + \sum_{k=1}^{n}\frac{4k}{k}\Bigg)$$

$$T(n) = 1 + 4\sum_{k=1}^{n}1$$

$$\underbrace{T(n) = 1 + 4n = O(n)}_{\text{average time complexity}}$$

---

WolframAlpha's string: T(0) = 1, n*T(n) = n*T(n-1) + 4n

Answer 2

The probability that $F_1(m)$ will ever get called is $\frac1{m+1}$. Here's why.

Whether $F_1(m)$ will get called or not is determined the first time that the random number we choose falls into the set $\{0, 1, \dots, m\}$. If it does not, then we call $F_1(m')$ for some $m'> m$, and the decision is simply postponed until another day. But if it does, then given that the random number falls into the set $\{0, 1, \dots, m\}$, the probability that it's $m$ is $\frac1{m+1}$: and if it's not $m$, we skip it.

Or to put it differently: if we ask "which of the numbers $\{0, 1, \dots, m\}$ is the first one we see returned from a call to random?" then until one of them does get returned, all of them remain possible, and so the answer is equally likely to be any of them, by symmetry. But $F_1(m)$ gets called exactly when $m$ is the first one on that list.

(Finally, if this still does not convince you - it's tricky to wrap your head around - then define $f_{m,n}$ to be the probability that $m$ ever gets called, starting from $n$. We'll have $f_{m,m+1} = \frac1{m+1}$, because the only way to ever call $m$ from $m+1$ is directly. In general, $$f_{m,n} = \frac1n + \frac1n f_{m,m+1} + \frac1n f_{m,m+2} + \dots + \frac1n f_{m,n-1},$$ and we can prove $f_{m,n} = \frac1{m+1}$ by induction on $n$.)

---

Now that we know this, we can compute the expected running time just by multiplying the number of print calls in $F_1(m)$, which is $2m+2$, by the probability that $F_1(m)$ is called, which is $\frac1{m+1}$. This product is $2$. So each of $F_1(0), \dots, F_1(n-1)$ contributes $2$ to the expected number of print calls, and $F_1(n)$ contains $2n+2$ more, for a total of $4n+2$ expected print calls. (Actually, it's $4n+1$ because $F_1(0)$ only includes one print call, not two. Whatever.) So the running time is $O(n)$.