Thanks for the response. I think it is a bit clearer.

I actually had a typo in the original algorithm and instead of j = 2 it should be x = 2 initially before entering the loop. But I guess the initial value of x does not make a difference to the runtime of the loop in terms of n.

So say I had this expression in the loop instead,

x = x * x

Then x would grow exponentially like this,

x = x*x*x*.....*x*X = x^i * X

where X is the initial value of x and i is the i'th iteration of the loop.

i = log base j (n/X)

In this case the runtime dependency of the loop on n would still be O(log n).

Would this be correct?