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?


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.

| cite | improve this answer | |

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.