@maobing I think about it this way: let dividend be D, divisor be S, n be the number of times we shift left. Because we know

S * [2^(n + 1)] > D (that's why we have to end the inner loop)

=> S * (2^n) * 2 > D

=> S * (2^n) > D/2

=> S * (2^n) > D - D/2

=> D - S * (2^n) < D/2

Now we know D - S * (2^n) < D/2.

D - S * (2^n) is the value we have after the inner loops end. It is less than D/2, which means everytime D decreases at least by half. Therefore the outer loop will execute at most logN time.

It is trivial to see inner loop execute logN time. Therefore the time complexity is O((logN)^2).

Divide Two Integers