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 ?

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

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

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – David Richerby May 1 '17 at 12:40
  • $\begingroup$ @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. $\endgroup$ – ratchet freak May 1 '17 at 12:48
  • $\begingroup$ 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. $\endgroup$ – David Richerby May 1 '17 at 12:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.