Time complexity of iterative division algorithm

Question

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'.

Answer 1

Can't guarantee my explanation is flawless, but here it is anyway:

Just as written in comments, the time complexity is O(n), i.e. linear. In other words, the time it takes for the computer to execute the algorithm increases linearly with the increase of x or the decrease of y. Example: it will take 3 loops to get the result if x = 10 and y = 3, and it will take twice as many loops if we increase x by two to equal 20. That's what they call O(n).

Other time complexity types that exist are O(n^2) - quadratic time (ex: you increase x by 2 and the number of required loops increases by 4), O(n^3) - cubic (same logic), O(logn) - logarithmic time (the time is increasing less than linearly and at some point almost stops to increase at all).

And finally, there's O(1) - constant time. The above algorithm can be improved to have constant time if you type q=x/y and r=x%y instead of using the loops.