Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose A(.) is a subroutine that takes as input a number in binary, and takes linear time (that is, O(n), where n is the length (in bits) of the number). Consider the following piece of code, which starts with an n-bit number x.

while x>1:

call A(x)


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

(a) How many times does the inner loop iterate (as a function of n)? Leave your answer in big-O form.

(b) What is the overall running time (as a function of n), in big-O form?

(a) O($n^2$)

(b) O($n^3$)

is this correct? can someone concur please, the way i think about it is that the loop has to compute two steps each time in cycles through and it will cycle through x time each time subtracting 1 from n bits until x reaches 0. And for part b since A(.) takes time O(n) we multiply that with the time it takes to execute the loop and we then have the over all running time. If i reasoned or did the problem wrong can someone please correct me and tell me what i did wrong.

share|improve this question

1 Answer 1

Supposing your code is as follows-- so that the inner-loop is both lines:

while (x>1) {
   call A(x)

the statements A(x) & x=x-1 run at O(n) time each, at each step of the loop-- asymptotically adding up to O(n).

The loop iterates x times-- that is directly proportional to the representation of n in decimal-- so the while statement iterates O(n)-- times.

The entire code executes in O(n)*O(n)=O($n^2$).

share|improve this answer
unfortunately i don't think this is correct since this is what i put down as my answer on my quiz and it was marked wrong. –  notamathwiz Oct 25 '13 at 2:55
math.stackexchange.com/users/63860/notamathwiz: curious - i'd check this w/the marker. this is the correct answer, and I don't think i'm missing anything. –  ashley Oct 25 '13 at 4:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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