algorithm - ケース 1 のマスター定理の証明: これらのステップはどのように数学的に導き出されるか?

Question

マスター定理の証明を理解するために Thomas H. Cormen の本を読んでいました。

ありがとう

Answer 1

最初の質問:

b^{\log_b(a)} = a

(SO に TeX はありませんか?)

これは、底に対する対数bが の逆数であるためですb^。では、a / a = 1こうしてb^epsilon残るだけです。

2 番目と 3 番目の質問:これは幾何級数です。ここで見つけることができます: https://en.wikipedia.org/wiki/Geometric_series#Formula
b^epsilon|b^epsilon| < 1