アルゴリズム：マスター定理

Question

マスター定理は、 T(n)= aT(n/b)+f(n)のような反復関係を解くのに使用できます。

f(n)=O(n)の場合、またはf(n)=cnの値が同じ場合は、 f(n)=cnについても マスター定理を使用できますか？

Answer 1

cが一定であることをAsummingと私が正しくあなたの質問を理解することが、解決策はcn = O(n)以来、f(n) = O(n)とf(n) = cnの両方で同じになりますので、マスターの定理はrecurranceを解決するために適用することができます。

Answer 2

私が質問を正しく理解した場合、f(n)=cn（ここではcは）はO(n)にあります。マスター定理を適用することができる。