Time complexity of simple recursive procedure with random variable

algorithmsdiscrete mathematicsrecurrence-relationsrecursionrecursive algorithms

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.

Best Answer

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

Related Question