I am trying to solve the following recurrence but I do not really get how I could do it.
Basically the task is very similar to CLRS page. 216-219. I already found the expected number of recursive calls. It is:
$\frac{2}{n} ∑_{k=\left\lfloor\frac{n}{2}\right\rfloor}^{n-1} E[T(k)] + 1$
I got it the following way:
I now the recurrence for the time is:
$ T(n) \leq $ $∑_{k=1}^{n} X_k T(max[k,n-k])+ Θ(n)$
and since I am interested in the expected number of recursive calls we have that $Θ(n) = 1 :
$ T(n) \leq $ $∑_{k=1}^{n} X_k T(max[k,n-k])+ 1$
So far I am sure.
I take the expectation and to more or less the same calculations like in the book and get:
$E[T(n)] \leq \frac{2}{n} ∑_{k=\left\lfloor\frac{n}{2}\right\rfloor}^{n-1} E[T(k)] + 1$
Unfortunately here I am stuck. Does anyone now how to solve the recurrence?
When it come to the expected number of time, the recurrence is:
$T(n) \leq \frac{2}{n} ∑_{k=\left\lfloor\frac{n}{2}\right\rfloor}^{n-1} E[T(k)] + Θ(n)$
They show that $E(T(n)) = O(n))$ and start by assuming $E(T(n)) \leq cn$ for a constant $c$ by substition. I understand how they do it, but I do not see what I want to show by assuming.
Would be great if anyone could help me.