0
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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<n$.

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}<n$, 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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Encipher
    Oct 5, 2021 at 23:52
  • $\begingroup$ 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 $\endgroup$
    – nir shahar
    Oct 6, 2021 at 7:59
  • $\begingroup$ Thanks. However as per my last question I would like to know that how could you convert inequality to equality? $\endgroup$
    – Encipher
    Oct 6, 2021 at 15:11
  • $\begingroup$ Why would you want equality? The inequality is between $T(n)$ and $20cn$ $\endgroup$
    – nir shahar
    Oct 6, 2021 at 16:17

Your Answer

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

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