Question

Estimate the complexity of algorithm 1 for finding the base b expansion of an integer n in terms of the number of divisions used.

Short answer

\(\)\(O(\log n)\)

Therefore exactly\(\left\lfloor {{{\log }_b}n} \right\rfloor + 1\) divisions are required, and this is\(O(\log n)\).

Step-by-step solution

Step 1

There is one division for each pass through the while loop. Also, each pass generates one digit in the base \(b\)expansion. Thus the number of divisions equals the number of digits in the base \(b\)expansion of \(n\).This is just \(\left\lfloor {{{\log }_b}n} \right\rfloor + 1\) (for example, numbers from \(10\) to\(99\) , inclusive, have common logarithms in the interval \((1,2))\) .

Step 2

Therefore exactly\(\left\lfloor {{{\log }_b}n} \right\rfloor + 1\) divisions are required, and this is\(O(\log n)\). ( we are counting only the actual division operation in the statement\(q: = \left\lfloor {{\raise0.7ex\hbox{$q$} \!\mathord{\left/

{\vphantom {q b}}\right.\kern-\nulldelimiterspace}

\!\lower0.7ex\hbox{$b$}}} \right\rfloor \) . is we also count the implied division in the statement \({a_k} = q\bmod b\), then there are twice as many as we computed here. The big \( - O\)estimate is the same, of course).