Karatsubaアルゴリズムの実行時間の計算方法は？

Question

私は式がT（n）= 3T（n/2）+ O（n）であることを知り、マスターメソッドを使ってT（n）= n ^（log3）を得ることができます。

しかし、私はまだマスター方法を使用せずに答えを得る方法がわかりません。再帰式から得られる結果はT（n）= 3 ^（logn）であり、2が基底であるからです。

誰でも私を助けることができれば、私は非常に感謝しています！

Answer 1

まあ、あなたは両方が同時に正しいからです。

n^(log3) = 3^(logn) 

証明：

y = 3^log(n) 
log(y) = log(n)*log(3) 
log(y)/log(n) = log(3) 

log<sub>n</sub>y = log(3)

y = n^(log3)