主方法 - 分析

Question

這是關於算法分析： 說，有問題的運行時間是：

T(n) = { 1, for n == 1 | T(n/3) + THETA(1), for n > 1} 

現在，這是THETA(log base3 n)

但是，如果我用法師的方法，我評估爲THETA(log base2 n)，使用案例二

我該如何從主方法得到正確答案？

Answer 1

它們是一樣的。對於任何兩個基地a和b,Θ(loga n) = Θ(logb n)，所以我們通常根本不提基地，只是說Θ(log n)。

這是因爲loga n = (1/logb a) * logb n，所以它們相差1/logb a，相對於n是不變的。