Time complexity of writing a number as power of 2's

Question

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 ?

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

Answer 1

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

• David Richerby: 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.
• ratchet freak: @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.
• David Richerby: 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.