Input: Two n-bit integers x and y, where y ≥ 1.
Output: The quotient and remainder of x divided by y.
if x = 0, then return (q, r) := (0, 0);
q := 0; r := x;
while (r ≥ y) do // takes n iterations for the worse case.
{
q := q + 1;
r := r – y
}; // O(n) for each r – y, where y is n bits long.
return (q, r);
For the above algorihtm which mainly focuses on dividing two 'n' bit integers 'x' and 'y', can somone please explain and let me know the time complexity in terms of 'n'.
See Question&Answers more detail:os