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

## 1 Answer

The first equation is the base case for the recurrence. The second equation represents the recurrence formula, on everything that isn't a base case.

Now, you can prove by induction this statemen, simply by using complete induction as follows:

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.

• The induction hypothesis is P(k )holds for an arbitrary integer k , need to proof that P (k + 1) is also true. I can not understand where do you use induction hypothesis? Additionally, T(n)<= 20cn/5+20c.3n/4+cn then, how could you make it equal to(=) 4cn+15cn+cn. Commented Oct 5, 2021 at 23:52
• 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 Commented Oct 6, 2021 at 7:59
• Thanks. However as per my last question I would like to know that how could you convert inequality to equality? Commented Oct 6, 2021 at 15:11
• Why would you want equality? The inequality is between $T(n)$ and $20cn$ Commented Oct 6, 2021 at 16:17