Time complexity of writing a number as power of 2's I'm wondering about the time complexity of writing a number as power of 2's. For example writing $n=218$ as $2 + 2^3 + 2^4 + 2^6 + 2^7$.
It seems to me that we do $\lceil log_2^n \rceil $ divisions. Each division costs $O(n^2)$ so an upper bound is $O(n^2 \cdot log_2^n)$. However, this seems like a very loose upper bound to me as the number we start with gets smaller with each division. So, what would be a better upper bound on the time complexity of writing an integer $n$ as power of 2's ?
 A: We assume that initial number has $d$ digits. The test for parity takes constant time, while the divisions by $2$ can be done in linear time $O(d)$ (halve the digits from left to right and carry to the right when odd). As this is repeated $d$ times, the global complexity is $O(d^2)=O(\log^2n)$.
[The length of the number indeed decreases on every division, but the net effect is only to halve the number of operations so that the complexity remains $O(d^2)$.]
A: The complexity of multi-precision arithmetic, Richard Brent, page 14 shows that the complexity of converting arbitrary base $\beta$ to base 2 has complexity $O(M(w) \log(w))$, where $w$ is the amount digits required to represent the number in base 2 and $M(w)$ is the time complexity of multiplying two $w$-bit integers. In your case $w = \lceil {\log_2 (n+1)} \rceil$.
If we use the Schönhage–Strasse algorithm for multiplication we get a total complexity of:
$O(w \cdot(\log w)^2 \cdot\log \log w) = O(\log n \cdot (\log \log n)^2 \cdot\log \log \log n)$
A: Using your algorithm that you suggest we can sum the work of all the divisions
$\sum_{i = 0}^{\log_2(n)} \left(\frac{n}{2^i} \right)^2 = \sum_{i = 0}^{\log_2(n)} \frac{n^2}{4^{i}} = n^2 \sum_{i = 0}^{\log_2(n)} \left(\frac{1}{4}\right)^i = 4n^2 \frac{1 - 4^{-\log_2(n) - 1}}{3} = \frac{4n^2}{3} (1 - 0.25n^{-2}) = \Theta(n^2)$
