{"id":10927,"date":"2022-09-25T12:24:30","date_gmt":"2022-09-25T06:54:30","guid":{"rendered":"http:\/\/jassweb.com\/solved\/solved-what-is-the-big-o-complexity-for-this-division-algorithm\/"},"modified":"2022-09-25T12:24:30","modified_gmt":"2022-09-25T06:54:30","slug":"solved-what-is-the-big-o-complexity-for-this-division-algorithm","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-what-is-the-big-o-complexity-for-this-division-algorithm\/","title":{"rendered":"[Solved] What is the Big O complexity for this division algorithm"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\n
\n
<\/div>\n
\n
\n

The number of iterations of the while-loop is exactly floor(x\/y)<\/code>. Each iteration takes n<\/code> operations, because that is the complexity of the subtraction r - y<\/code>.<\/p>\n

Hence the complexity of the algorithm is n * floor(x\/y)<\/code>. However, we want to express the complexity as a function of n<\/code>, not as a function of x<\/code> and y<\/code>.<\/p>\n

Thus the question becomes: how does floor(x\/y)<\/code> relate to n<\/code>, in the worst case?<\/p>\n

The biggest value that can be obtained for x\/y<\/code> when x<\/code> and y<\/code> are two nonnegative n<\/code>-digits numbers, and y >= 1<\/code>, is obtained by taking the biggest possible value for x, and the smallest possible value for y.<\/p>\n