Time Complexity of the below code?
It is $O(\log^2 \frac{\text{dividend}}{\text{divisor}})$.

The inner loop clearly takes at most $O(\log \frac{\text{dividend}}{\text{divisor}})$ time since initially $k= \text{divisor}$ and it is doubled at every iteration.

The outer loop requires at most $O(\log \frac{\text{dividend}}{\text{divisor}})$ iterations since the inner loop subtracts from $\text{dividend}$ the highest multiple $x = k \cdot \text{divisor}$ such that $k=2^i - 1$ for some integer $i$ and $x \le \text{dividend}$.
This is true because initially $k \le \log ( 1+ \frac{\text{dividend}}{\text{divisor}})$ and the same value of $i$ cannot be selected more than two times in a row since $3 \cdot (2^i - 1) = 3 \cdot 2^i - 3 = 2^{i+1} + (2^i-3) \ge 2^{i+1} - 1$.



This analysis is tight in the following sense:
let $\text{divisor}=1$ and $S_j = \sum_{i=0}^j (2^i - 1)$. Let $\text{dividend}= S_\ell$ for some $\ell \ge 2$ of choice.

Clearly $S_j &gt; 2^j - 1$. Moreover, we can show by induction on $j$ that $S_j &lt; 2^{j+1}-1$.

The base case $j=0$ is trivial: $S_0 = 0 &lt; 2^1 - 1 = 1$.
Suppose now that the claim is true for $j-1$:
We have $S_j = S_{j-1} + (2^j - 1) &lt; 2^j - 1 + (2^j - 1) = 2^{j+1} - 2$.

This means that when divisor is $S_j$, the inner loop will subtract $2^{k}-1$ where $k=j$ (in $k-1$ iterations), and the divisor will become $S_{j-1}$. It follows that $\ell$ iterations of the outer loop are needed to reach $S_0 = 0$.

The overall number of iterations of the inner loop is then:
$$
\sum_{i=1}^\ell (i-1) = \sum_{i=0}^{\ell-1} i = \frac{\ell (\ell-1)}{2} = \Theta(\ell^2).
$$

But $\ell \ge \log S_\ell$, since $S_\ell$ has at least $\ell$ binary digits and hence the above quantity is $\Omega(\log^2 S_\ell) = \Omega(\log^2 \text{dividend}) = \Omega(\log^2 \frac{\text{dividend}}{\text{divisor}})$.