2
$\begingroup$
int function(int n)
{
   int i;

   if (n <= 0) {
       return 0;
   } else {
       i = random(n - 1);
       return function(i) + function(n - 1 - i);
   }
}

Consider the recursive algorithm above, where the random(int n) spends one unit of time to return a random integer which is evenly distributed within the range [0,n]. If the average processing time is T(n), what is the value of T(6)T(6)?

(Assume that all instructions other than the random cost a negligible amount of time.)


This question was on Brilliant and I was following along their solution

              T(n)=T(i)+T(n−1−i)+1
              T(n)=T(0)+T(n−1)+1
              T(n)=T(1)+T(n−2)+1
                    ....
              T(n)=T(n−2)+T(1)+1
              T(n)=T(n−1)+T(0)+1

       nT(n)=2(T(0)+T(1)+....+T(n−2)+T(n−1))+n..........(1)
       (n−1)T(n−1)=2(T(0)+T(1)+...+T(n−2))+n−1).........(2)

Subtract 1 from 2

            nT(n)−(n−1)T(n−1)=2T(n−1)+1

$\frac{T(n)}{n+1}$ = $\frac{T(n-1)}{n}$ + $\frac{1}{n(n+1)}$. They mention this is a telescoping sequence.

They say T(0) = 0 and then get

$\frac{T(n)}{n+1}$ = $\frac{1}{(1)(2)}$ + $\frac{1}{(2)(3)}$ + ... + $\frac{1}{n(n+1)}$ = $\frac{n}{n+1}$. I do not understand how they got to this equation from the previous. ​

$\endgroup$
1
$\begingroup$

Let $S(n) = T(n)/(n+1)$. Notice that $S(0) = 0$ and $S(n) = S(n-1) + 1/n(n-1)$. Thus $$ S(n) = \frac{1}{n(n+1)} + S(n-1) = \frac{1}{n(n+1)} + \frac{1}{(n-1)n} + S(n-2) = \cdots $$ Continuing in this way, for any $i \geq 0$ we get $$ S(n) = \frac{1}{n(n+1)} + \frac{1}{(n-1)n} + \cdots + \frac{1}{(i+1)(i+2)} + S(i). $$ In particular, for $i = 0$ we get $$ S(n) = \frac{1}{n(n+1)} + \frac{1}{(n-1)n} + \cdots + \frac{1}{(1)(2)}. $$


Alternatively, you can prove by induction that $S(n) = n/(n+1)$. This clearly holds for $n = 0$. Assuming it holds for $n-1$, we prove it for $n$: $$ S(n) = \frac{1}{n(n+1)} + S(n-1) = \frac{1}{n(n+1)} + \frac{n-1}{n} = \frac{1+(n-1)(n+1)}{n(n+1)} = \frac{n^2}{n(n+1)} = \frac{n}{n+1}. $$


Alternatively, we can prove directly that $T(n) = n$ by induction. This clearly holds for $n = 0$. Assuming it holds for $n-1$, we prove it for $n$: $$ T(n) = \frac{n+1}{n} T(n-1) + \frac{n+1}{n(n+1)} = \frac{n+1}{n} \cdot (n-1) + \frac{1}{n} = \frac{(n+1)(n-1)+1}{n} = \frac{n^2}{n} = n. $$

$\endgroup$
1
  • $\begingroup$ Great explanation, thanks very much. $\endgroup$ – user2643729 Apr 7 '20 at 16:41

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.