# 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.

## 1 Answer

"since $$T(n)=O(n)$$ then $$T(n)=an+b$$" 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.