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.
The one loop that you see is for number of additions. But it is also assuming number of bits to be to the order of n. For one iteration, you will perform operation over O(n) bits. For n iterations, it will be to the order of n squared.