Question

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.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top