Exact runtime of median of median algorithm Consider median of median algorithm. If I make to group of size $7$ instead of $5$ then the recurrence equation will be
$$T(n)=T(n/7)+T(5/7\cdot n+4)+O(n),$$
which can be proven by induction equal to $O(n)$.
Assume it takes around $14$ steps to sort group of $7$ elements. How do I find exact runtime if I want to find $k$th smallest element in sequence, by exact run time I mean a solution for above recurrence.
My idea was that since $T(n)=O(n)$ then $T(n)=an+b$ ,where $a $ or $b$ might be depend on value of $k$. How can I find value of $a$ and $b$ or it is impossible to find value of $b$, as value of $a$ can be found but I am not sure how.
&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.