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?? How did we get the sum??
The relation describes expected runtime. Each stage of recursion creates two subproblems of size $x$ and $n-x$, where $x$ is a random variable uniformly distributed over $\{1, ..., n\}$. What we are modeling is the probability that our pivot element is the $x^{th}$ largest element. Our hypothesis is that there is an equal probability for it to be any of the $1^{st}$ through $n^{th}$ largest elements.
$$T(n)=\sum_{i=1}^{n}\frac{1}{n}[T(i-1)+T(n-i)]+\Theta(n)$$
The $\Theta(n)$ term is the time associated with performing the partition around the pivot element.
Put another way, we can think of $\mathcal{T}_n$ as a random variable corresponding to the runtime of quicksort on a random permutation of the elements $\{1, ..., n\}$. Then $T(n) = \mathbf{E}[\mathcal{T}_n]$.