漸近增長率 「INT I =常量1;而（ⅰ<N）{I * = CONSTANT2;}」

Question

什麼是這個函數的漸近增長率：

int i=3; 
while(i < n) { 
    i *= 5; 
} 

我測量它：

當n=3i<n執行1次

。 。

當n=16i<n被執行2次

。 。

時n=80，i<n被執行3次

。 。

我需要找到正確的增長率，但我卡住了。

Answer 1

我認爲增長速度是：

3 * 5^x >= n 
5^x >= n/3 

因此

xlog5 >= log n - log 3 
x >= (log n - log 3)/(log 5) 

可以定義3*5^x必須>=n。我們可以用這個基礎在第一行中設置方程。