So I am trying to figure out the recurrence relation for the median of medians algorithm using groups of 3 instead of groups of 5. Per CLRS's method, my recurrence relation looks like

$$ T(n) = T(\lceil \frac{n}{3} \rceil) + T(\frac{2n}{3} + 4) + c_1n $$

And I want to show $T(n) = O(n \lg n)$

Via substition, I assume inductively that

$T(n') = cn' \lg n'$

So by substition

$$T(n') \leq c\lceil \frac{n'}{3} \rceil \lg \lceil \frac{n'}{3} \rceil + c(\frac{2n'}{3} + 4) \lg (\frac{2n'}{3} + 4) + c_1n' $$

$$ \leq c (\frac{n'}{3} + 1) \lg (\frac{n'}{3} + 1) + c(\frac{2n'}{3} + 4) \lg (\frac{2n'}{3} + 4) + c_1n'$$

aaand now im stuck. Is there anyway i can drop the +1 and +4 from this expression to make it simpler?


1 Answer 1


You can use the inequality $\log (1+x) < x$ (valid for $x > 0$, where $\log$ is the natural logarithm), which follows from a Taylor expansion, to reason as follows: $$ \log \left(\frac{n'}{3} + 1\right) = \log \left(\frac{n'}{3} \cdot \left(1 + \frac{3}{n'}\right)\right) = \log \frac{n'}{3} + \log \left(1 + \frac{3}{n'}\right) < \log \frac{n'}{3} + \frac{3}{n'}. $$ This shows (after some calculation) that you can remove the $+1$ and $+4$ in return for an additional constant additive term, that is, you can estimate your final line by $$ c \left(\frac{n'}{3}+1\right) \lg \frac{n'}{3} + c\left(\frac{2n'}{3}+4\right) \lg \frac{2n'}{3} + M + c_1 n', $$ where $M>0$ is some constant.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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