QuickSelect with Median of Medians runtime I know that Median of medians itself is $O(n)$.
With a good pivot, QuickSelect is $O(n)$, too -- but with a bad one, it's $O(n^2)$.
But if I now were to use the element gotten through median of medians as the pivot for QuickSelect, what would the new worst-case runtime of QuickSelect be? Would it be $O(n)$ guaranteed too? 

Why would it not be $O(n\log n)$? I'm a bit confused, I guess. Since we have to choose the median of medians, which takes $O(n)$, for each subproblem, and we have $\log n$ subproblems (always recursing on one side of the median).
The medians of medians algorithm will return a pivot with a rank between $\frac{3}{10}n$ and $\frac{7}{10}n$ in time $O(n)$.

You can then describe the worst-case computational complexity of Quickselect on an instance of $n$ elements with the following recurrence relation:
$$
T(n) = T\left(\frac{7}{10}n\right) + O(n),
$$
where $O(n)$ accounts both for the work needed to run the median-of-medians algorithm an for the partitioning of the input. 

Unrolling the recursion shows that (you can prove this formally by induction):
$$
T(n) \le c n \sum_{i=0}^{+\infty} \left( \frac{7}{10} \right)^i = cn \cdot  \frac{1}{1-\frac{7}{10}} = \frac{10cn}{3} = O(n),$$

where $c&gt;0$ is a suitable constant (hidden in the $O(n)$ notation of the recurrence relation).