0
$\begingroup$

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 ?

$\endgroup$
5
  • 1
    $\begingroup$ If the integer $n$ is input in binary it gets very easy... $\endgroup$
    – Pontus
    Commented Apr 20, 2017 at 11:27
  • $\begingroup$ No it's given in decimal. $\endgroup$
    – SpiderRico
    Commented Apr 20, 2017 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
    Commented Apr 20, 2017 at 11:39
  • 1
    $\begingroup$ Are you sure that a division costs $O(n^2)$? $\endgroup$
    – xavierm02
    Commented Apr 20, 2017 at 11:44
  • 2
    $\begingroup$ What is your model of computation? $\endgroup$ Commented Apr 20, 2017 at 13:54

1 Answer 1

3
$\begingroup$

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

$\endgroup$
3
  • $\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$ Commented May 1, 2017 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$ Commented May 1, 2017 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$ Commented May 1, 2017 at 12:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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