May you solve this: What is complexity of this algorithm?

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

CodePudding user response：

Consider sequence of i at every step:

 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

So we can see polynom for m, and it is known that

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

This expression should reach n, so rough estimation is

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

We can ignore logarithm base, so number of steps and number of operations (there is constant number of operations per loop step) is estimated as O(log(n))