"int i=constant1; while(i < n) { i *= constant2; }" 的渐近增长率

Question

这个函数的渐近增长率是多少：

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

我测量了它：

当n=3 i<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。我们可以以此为基础在第一行建立方程

Asymptotic growth rate of "int i=constant1; while(i < n) { i *= constant2; }"