0
$\begingroup$

The algorithms below has been taken from Discrete Mathematics and it's Applications 7th edition book by Rosen.

enter image description here

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.

enter image description here

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.

$\endgroup$
2
$\begingroup$

Time complexity is often about the number of loop operations, but not always.

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy