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)

x=x-1

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

2 Answers 2

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

while (x>1) {
   call A(x)
   x=x-1
}

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

From the looks of it, this array will run infinitely due to the fact that the recursive element is called before x is decremented, thus the function will never terminate.

If you called x=x-1 before you recursively called A, then that would allow the function to effectively decrement at each level of recursion and thus terminate after x amount of times.

Also, it appears that you do not understand what big-O time complexity means, the fact is whether n = 1 or n = 10000000000000000000000 this has no effect on whether a function is O(n) or O(n^2), as these are related to the exponential nature of the function, not linear (such as a loop iterating x amount times within another loop that iterates x amount times). Addition, subtraction, multiplication, and division are all linear thus are all going have a time complexity of O(n), as well will calling functions, declaring variables, and performing tests ( such as x > 0).

(a & b) in your code the loop iterates until you force-quit the program... if you set the code up properly however then the while test = n, the decrement = n-1 (because it will run one time less than the condition and is not related to the decrement whatsoever), and the recursive call will also = n-1. So... the formula you are looking for for this program is n + (n-1) + (n-1) for all all values where n is greater than 1, otherwise it the total cost would be simply one. for example...

if n < 2 then the cost would be 1 (for the test only). if n < 2, then the cost would be n + (n-1) + (n-1) if in was 2 then the cost would be 2 + (2-1) + (2-1)

The time complexity, being that there are no exponential aspects within the function is, and always will be, Big-O of n (O(n)).

share|improve this answer

Your Answer

 
discard

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.