Search code examples
algorithmmaster-theorem

Proof of Master theorem for Case-1: How these steps are mathematically derived?

I was reading Thomas H. Cormen book to understand the Proof of Master theorem.However, i am stuck at proving case-1.please help me to understand the mathematical proofs by more easy mathematical derivation of steps in the following image:

enter image description here

Thanks

Solution

  • For the first question:

    b^{\log_b(a)} = a

    (Don't we have TeX in SO?)

    This is because the logarithm to the base b is the inverse of b^. Then a / a = 1, thus only b^epsilon remains.

    Second and third question: This is the geometric series, you can find it here: https://en.wikipedia.org/wiki/Geometric_series#Formula
    For this the summand b^epsilon must be between zero and one (exclusive), i.e. |b^epsilon| < 1.