What's time complexity of this loop?

R = 40;
while(R>=10){
  x = x-1;
  R = R div 2;
}

I really appreciate if you explain it to me, too.

CodePudding user response：

Each cycle the R is reduced to half.

Therefore O(log_2 R)

If R=40 cannot be changed, then the loop will just run 3 times therefore it is constant and O(1)

CodePudding user response：

Time complexity will be O(log₂R).

Idea is that the R will get divided by 2 every time it enters the loop. R/2, R/2², R/2³...

At some point R/2^x = 10.
So which equates to 2^x = (R/10)
and x = log₂(R/10).

Since this appears to be close to log₂R we can say its ~ O(log₂R)