# Time-complexity for basic multiplication and division algorithms

The algorithms below has been taken from Discrete Mathematics and it's Applications 7th edition book by Rosen. p.253 says that "number of shifts required is $$O(n^2)$$" and "a total of $$O(n^2)$$ additions of bits are required for all n additions".

Why isn't this algorithm $$O(n)$$? I can see only two non-nested for loops. p.254 says that "this means that we need $$O(n^2)$$ bit operations to find the quotient and remainder when a is divided by d".

Why isn't this algorithm $$O(n)$$? I can see only one while loop.

In the multiplication algorithm, the step $$b := b + c_j$$ is actually adding two n-bit numbers. Adding two n-bit numbers is not an elementary operation, but takes itself O(n) steps, so the second loop has n iterations, each iteration runs in O(n), therefore a total of $$O(n^2)$$.
The division algorithm is totally off. There is only one loop (but same as before, each iteration takes O(n)). However, look carefully how many iterations the loop has. It doesn’t have n iterations, the number of iterations can be much much higher. The algorithm is very much suboptimal. How many iterations for 64 bit signed integers if $$a = 2^{63}-1$$ and d = 1?