0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ the squaring i assume is because A(.) itself takes O($n^2$) time. but idk if thats right. and part B i have no idea $\endgroup$ – notamathwiz Oct 25 '13 at 4:56
  • $\begingroup$ But A is just the subtract or divide, which is given as O(n). The point of b is there are exponentially many runs through the loop $\endgroup$ – Ross Millikan Oct 25 '13 at 13:10

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.