patternMinor
Median of Medians Recurrence Relation for 3-grouping
Viewed 0 times
mediansgroupingrecurrencemedianforrelation
Problem
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?
$$
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?
Solution
You can use the inequality $\log (1+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) 0$ is some constant.
$$
\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) 0$ is some constant.
Context
StackExchange Computer Science Q#87992, answer score: 3
Revisions (0)
No revisions yet.