consider the following subroutine, what is the running time

Question

Suppose A(.) is a subroutine that takes as input a number in binary, and takes time O($n^2$), where n is the length (in bits) of the number.

(a) Consider the following piece of code, which starts with an n-bit number x.

while x > 1:

call A(x)

x = x/2

Assume that the division by two takes O(n) time on an n-bit number.

On the first iteration of the inner loop, x is n bits long. What is the length of x during the second iteration? The third iteration?

How many times is the inner loop executed? Leave your answer in big-O form.

What is the overall running time (in terms of n)? Again, use big-O.

Is this a polynomial-time algorithm?

(b) Now answer the same questions for this alternative piece of code.

while x > 1:

call A(x)

x = x - 1

Assume that the subtraction operation takes O(n) time on an n-bit number.

---

SOLUTION

(a) On each iteration of the inner loop, x is halved and thus shrinks by one bit. Thus there are at most n iterations. The overall running time is O($n^2 + (n - 1)^2 + ... + 1^2$) = O($n^3$), polynomial.

(b) On each iteration of the inner loop, x decreases by just 1. Thus its length remains the same for roughly $2^{n-1}$ iterations, then for $2^{n-2}$ iterations, and so on. The overall running time is O($n^22^n$), exponential.

part a i think i understand, i just took a an example 8 which is 1000 in binary and each time its halved it shrinks by one bit from 8 (1000) to 4 (0100) to 2 (0010) to 1 (0001), i can see concretely the reasoning behind part a. Part B is a bit more confusing i dont understand how they come up with the iterations and the running time, can someone please explain

Answer 1

For a, I don't understand squaring the length of $x$. You are told that one division is $O(n)$, so I would have said $n + (n-1)+(n-2)+\dots+1=O(n^2)$. For b, it takes $2^{n-1}$ subtractions to take one bit off $x$, because an $n$ bit number has its most significant bit worth $2^{n-1}$ and you have to subtract it away. Again I don't understand the square on $n$, I would have said $n2^{n}$, though it is a little lower than that, caused by the number shrinking.