5.6 Compute x/y
The book mentions at the end of the solution that: “Therefore, assuming individual shift and add operations take O(1) time, the time complexity is O(n).”
I have trouble understanding the solution as being O(n). There is a while loop that is nested in a while loop in the solution. Wouldn’t that still make the solution O(n^2) regardless of the time it takes for individual shift and add operations?
I might be missing something here. Your clarification would be much appreciated 
-H
Hey @fhani,
It is exactly O(n) since the inner while loop is at most doing 32 times during the overall execution, and the outer while loop is going through O(n) bits. So this is O(n) eventually.
Please let us know if you have any questions.
Hi @tsunghsienlee,
Thank you for your explanation. But I seem to be missing something basic, why does the outer while loop go through iterations = bits used to represent x/y.
Every iteration is working with minimum ‘a’ or Max ‘a+1’ bits at a time, where a is the total number of bits used to represent y (going by the grade school binary division algorithm).
If total bits used to represent x = ‘b’, then total number of iterations would be ‘b’/‘a’ which is what the book says. Is my understanding correct?
Intuitively the time complexity seems right, and when I test with examples, ofcourse it is right, but I am unable to prove it on paper using frequency count or assumption methods.
Could you please elaborate on this?