# how long does this subroutine and loop take

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.

-

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

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

-