CODEWITHSUNDEEP
python-3.xtime-complexity
Prashin Jeevaganth
Prashin Jeevaganth

Reputation: 1343

Python: Time and space complexity of gcd and recursive iterations

I’m studying for mid-terms and this is one of the questions from a past yr paper in university. (Questions stated below) Given Euclid’s algorithm, we can write the function gcd.

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

[Reduced Proper Fraction] Consider the fraction, n/d , where n and d are positive integers. If n < d and GCD(n,d) = 1, it is called a reduced proper fraction. If we list the set of reduced proper fractions for n <=8 in ascending order of size, we get: 1/8,1/7,1/6,1/5,1/4,2/7,1/3,3/8,2/5,3/7,1/2,4/7,3/5,5/8,2/3,5/7,3/4,4/5,5/6,6/7,7/8 It can be seen that there are 21 elements in this set.

Implement the function count_fraction that takes an integer n and returns the number of reduced proper fractions for n. Assuming that the order of growth (in time) for gcd is O(logn), what is the order of growth in terms of time and space for the function you wrote in Part (B) in terms of n. Explain your answer.

Suggested answer.

def count_fraction(n):
    if n==1:
        return 0
    else:
        new = 0
        for i in range(1,n):
            if gcd(i,n) == 1:
                new += 1
        return new + count_fraction(n-1)

The suggested answer is pretty strange as the trend of this question in previous years, is designed to test purely recursive/purely iterative solutions, but it gave a mix. Nevertheless, I don’t understand why the suggested order of growth is given as such. (I will write it in the format, suggested answer, my answer and questions on my fundamentals)

Time: O(nlogn), since it’s roughly log1+log2+· · ·+log(n−1)+logn

My time: O(n^2 log n). Since there is n recursive function calls, each call has n-1 iterations, which takes O(log n) time due to gcd.

Question 1: Time in my opinion is counting number of iterations/recursions* time taken for 1 iteration/recursion. It’s actually my first time interacting with a mixed iterative/recursive solution so I don’t really know the interaction. Can someone tell me whether I'm right/wrong?

Space: O(n), since gcd is O(1) and this code is obviously linear recursion.

My space: O(n*log n). Since gcd is O(log n) and this code takes up O(n) space.

Question 2: Space in my opinion is counting number of recursions*space taken for 1 recursive call OR largest amount of space required among all iterations. In the first place, I would think gcd is O(log n) as I assume that recursion will happen log n times. I want to ask whether the discrepancy is due to what my lecturer said.

(I don’t really understand what my lecturers says about delayed operations for recursions on factorial or no new objects being formed in iteratives. How do u then accept the fact that there are NEW objects formed in recursion also no delayed operations in iteration).

If u can clarify my doubt on why gcd is O(1) instead of O(log n), I think if I take n*1 for recursion case, I would agree with the answer.

Upvotes: 0

Views: 3339

Answers (1)

Blckknght
Blckknght

Reputation: 104712

I agree with your analysis for of the running time. It should be O(n^2 log(n)), since you make n calls to gcd on each recursive call to count_fraction.

You're also partly right about the second question, but you get the conclusion wrong (and the supplied answer gets the right conclusion for the wrong reasons). The gcd function does indeed use O(log(n)) space, for the stack of the recursive calls. However, that space gets reused for each later call to gcd from count_fraction, so there's only ever one stack of size log(n). So there's no reason to multiply the log(n) by anything, only add it to whatever else might be using memory when the gcd calls are happening. Since there will also be a stack of size O(n) for the recursive calls of count_fraction, the smaller log(n) term can be dropped, so you say it takes O(n) space rather than O(n + log(n)).

All in all, I'd say this is a really bad assignment to be trying to learn from. Almost everything in it has an error somewhere, from the description saying it's limiting n when it's really limiting d, to the answers you describe which are all at least partly wrong.

Upvotes: 1

Related Questions