runtime - 再発を解く: T(n)=3T(2n/3)+1

Question

再発の実行時間と、T(n)=3T(2n/3)+1それをどのように取得したか?

Answer 1

マスター定理を使用します。元の質問で試したように、再発を自分で解決しようとするよりもはるかに簡単です。

OTTOMH これでわかるはずですT(n) = Theta(n^2.7)(マスター定理のケース 1)。