# 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_2n \rceil$ divisions. Each division costs $O(n^2)$ so an upper bound is $O(n^2 \cdot \log_2n)$. 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 ?

• If the integer $n$ is input in binary it gets very easy... – Pontus Apr 20 '17 at 11:27
• No it's given in decimal. – SpiderRico Apr 20 '17 at 11:33
• In which case what you are asking is about the time complexity of converting a number from decimal to binary. This is well-studied. – Pontus Apr 20 '17 at 11:39
• Are you sure that a division costs $O(n^2)$? – xavierm02 Apr 20 '17 at 11:44
• What is your model of computation? – Yuval Filmus Apr 20 '17 at 13:54

## 1 Answer

Division by 2 is linear in the number of digits (lets call that $s$) $O(s)$ aka. $O(\log n)$.

output = [];
bool carry;
for(digit in digits){ // most significant digit first
if(carry) digit+=10;

carry = isOdd(digit);
push_front(output, floor(digit/2));

}
if(output.front == 0) pop_front(output);
//carry is the new bit to push to the front of the result
// and output is the new digit array


Because the number of digits decreases with a constant rate (1 digit every 3 to 4 divisions). This algorithm results in a $O(s^2)$ time complexity aka. $O(\log^2 n)$.

• I have to say, I find this code incomprehensible. In what order does the for loop iterate through the digits? What do push_front and pop_front do? What is output.front? I think it would be much clearer just to assume the input is an array of digits indexed 1..s with either the most- or least-significant first, according to convenience. – David Richerby May 1 '17 at 12:40
• @DavidRicherby it's a bit of a mix mostly inspired by the C++ naming convention for its std containers, and digits are processes most significant digit first. – ratchet freak May 1 '17 at 12:48
• Thing is, the point of pseudocode is precisely to avoid people having to understand or even be familiar with the gigantic tentacular mess that is the C++ standard library. – David Richerby May 1 '17 at 12:55