Median of medians algorithm My question is I don't understand how we determine the constant in T(T(n/3), T(n/5)). For example, we divide elements into 9 groups and get a formula like this
T(n) <= T(n/9) + T(7n/9) + O(n)
I don't understand how we get 7n/9, why is it not 5n/9, 8n/9, or something else?
This question comes from the task.
"Does the algorithm "Median of Medians" run in linear time, if one uses blocks of three or blocks of nine?"
 A: Wikipedia has a good explanation here. The relevant sections are "Properties of pivot" and "Proof of $O(n)$ running time". I'll still explain the idea here, but you can find more details on the Wikipedia page.
In the quickselect / "median of medians" algorithm, you do three things at each recursive step. First, you break into small chunks (you're using chunk size 9) and find the median of all those chunks in $O(n)$ time. Second, you find the median of all the chunk medians; there are $\frac n 9$ of these, so this will take $T\left(\frac n 9 \right)$ time.
Finally, once you compute that median-of-medians (call it $M$), you'll use it as a pivot. $M$ guaranteed to be bigger than $\frac{n/9}{2}$ of the chunk medians, and if it's bigger than the median of a chunk then it must be bigger than the 4 smaller elements in that chunk as well. Therefore $M$ will be greater than at least $5 \cdot \frac{n/9}{2} = \frac{5n}{18}$ elements from the array. Using essentially the same argument we can show $M$ will also be smaller than at least $\frac{5n}{18}$ elements.
We'll need to recursively call our algorithm on the larger of the two "sides" created by using $M$ as a pivot. Due to the bounds above, the larger side will have size $\le n - \frac{5n}{18} = \frac{13n}{18}$. That means the final term we need to add on the RHS is $\mathbf{T\left(\frac{13n}{18}\right)}$.
Note I got a slightly different term from the one you quoted: $\frac{13n}{18} < \frac{7n}{9}$. Mine gives a slightly tighter bound. I'm not sure where you got your term but I'm guessing it was obtained by being a little less careful when deciding how many elements must be smaller than $M$. It doesn't really matter to the proof in the end, since you'll still get the $O(n)$ time complexity either way, but I think my version of the term is "slightly better".
