3

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 ?

SpiderRico
  • 483
  • How is the initial number represented ? –  Apr 20 '17 at 11:05
  • It's represented as decimal. – SpiderRico Apr 20 '17 at 11:06
  • Such as BCD or ASCII ? –  Apr 20 '17 at 11:06
  • If you want to output a number as binary, in your example $n = 11011010_2$, then you need to use at least $\log n$ time, since the bit-length of your number will be $\lceil \log_2 n \rceil + 1$. – Joppy Apr 20 '17 at 11:08
  • @Joppy but what about the cost of divison ? – SpiderRico Apr 20 '17 at 11:10
  • 1
    How do you get division by 2 to have order $n^2$? To me it's at most order $\log_{10} n$ (or order $n$, depending on whether $n$ is the number itself or the number of digits), since you do one digit at the time. – Arthur Apr 20 '17 at 11:13

3 Answers3

4

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)$.]

1

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)$

orlp
  • 10,508
0

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)$

BenB
  • 837