这个算法的复杂度是多少？

Question

你能解决这个问题吗：这个算法的复杂度是多少？

for(int i=0;i<n;i++)
   i*=m;

Answer 1

在每一步考虑 i 的序列：

 0    =>  0
 1    =>  m
 m+1  =>  m^2+m   
 m^2+m+1 => m^3+m^2+m
 m^3+m^2+m+1 => m^4+m^3+m^2+m

所以我们可以看到m的多项式，并且已知

m^k+m^(k-1)+...+1 = m^(k+1)/(m-1)    //might be checked with multiplication by (m-1)

这个表达式应该达到n个，所以粗略估计是

 m^k~n
 k = log(n) base m   //number of steps

我们可以忽略对数底数，因此步骤数和操作数（每个循环步骤的操作数是常数）估计为O(log(n))

What is complexity of this algorithm?