Exact runtime of median of median algorithm
&quot;since $T(n)=O(n)$ then $T(n)=an+b$&quot; it's wrong assumption, because big-$O$ gives only upper bound. For example $n^\alpha \in O(n)$ for $\alpha \in (0,1))$, $\log n \in O(n)$ etc., so you cannot reduce situation for only linear functions.
For exact estimation you need to elaborate $O(n)$ in recurrence relation.