# Proof the recurrence relation of order statistics using induction

I read order statistics from the book The Design and Analysis of Computer Algorithms", by Aho, Hopcroft, Ullman, Addison-Wesley

As per the algorithm the recurrence relation given

T(n)<= cn for n<=49 .....1

T(n)<= T(n/5) + T(3n/4) + cn for n>=50 .....2

How can I prove it by induction T(n)<= 20cn?

I have two more questions

For the 1st equation why they define n<=49 and for the 2nd equation n>=50

Thank you.

The base case is obviously correct. For the induction hypothesis, assume correctness for any $$k.
Now, for $$T(n)$$, we can use the recurrence formula to get $$T(n)=T\left(\frac{n}{5}\right) + T\left(\frac{3n}{4}\right) + cn$$ And notice that $$\frac{n}{5},\frac{3n}{4}, and hence we can use the induction hypothesis on them. Doing so, will yield: $$T(n)\le \frac{20cn}{5}+\frac{20c\cdot 3n}{4}+cn=4cn+15cn+cn=20cn$$ And hence we also proved that $$T(n)\le 20cn$$ and with that we completed the induction proof.
• Complete induction assumes $P(k)$ for all $k<n$, and you will have to prove $P(n)$. For your other doubt, the equality is between $20cn/5+20c\cdot3n/4+cn$ and $4cn+15cn+cn$, its just writing a simpler form for the same value Oct 6, 2021 at 7:59
• Why would you want equality? The inequality is between $T(n)$ and $20cn$ Oct 6, 2021 at 16:17