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 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.