What is complexity of this algorithm?

Question

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

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

Answer 1

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))