Quicksort-How did we get the relation?

[mathmari]

Hey!

At the proof of the theorem that the expected time of Quicksort is $O(n \log n)$, there is the following sentence:

We suppose that the partitions are equally likely, so the possibility that the sizes of the sequences $S_1$ and $S_3$ are $i-1$ and $n-i$, respectively, is $\frac{1}{n}$.

Let $T(n)$ be the expected time of Quicksort.

Taking into consideration all the possible values of $i$, we get the relation: $$T(n)=\sum_{i=1}^{n}\frac{1}{n}[T(i-1)+T(n-i)]+\Theta(n)$$Could you explain to me how we get the above relation?? (Wondering) How did we get the sum?? (Wondering)

 

[Future Bruno]

The relation above comes from the fact that for any partition of the array into two subarrays, the expected time of Quicksort is the sum of the expected times of the two subarrays plus the cost of the partition itself.The sum over $i$ in the equation is taking into account all the possible partitions of the array into two subarrays. For each possible value of $i$, we have a different partition of the array and thus a different expected time. The $\frac{1}{n}$ is the probability of each partition occurring. Therefore, the equation is summing up all the expected times for each possible partition, with the probability weighting each term.