python generators time complexity confusion

Question

I have been reading about keyword yield and generators in python and I want to know if I have understood it right it terms of time complexity.

Here is my generator function to get factors:

def calc_factors(n):
    for k in range(0, n+1):     # this is the second "for" loop
        if n % k == 0:
           yield k

and I would call this generator function as:

>>> for factor in calc_factor(100):   # this is the first "for" loop
        print factor

Now my understanding is that this has time complexity of O(n^2) as it has two for loops but again I'm not convinced. Please enlighten me on this front. Thanks in advance!

Answer 1

You misunderstood. You have a O(n) loop. The loop over the generator function is not a nested loop, it merely receives each item from the generator as it is yielded.

In other words, the for factor in calc_factor(100) loop is directly connected to the yield k expression; each time that executes the for factor in calc_factor(100) loop advances one step. You get 1 factor value for every yield k expression executed. yield k executes (up to) n times, no more.

You can, without bending the truth too much, imagine all code in the for factor in calc_factor(100) loop body as replacing the yield k line, with factor = k. In your case you only use print factor, so you could replace the yield k with print k with no loss of functionality.

If you want to look at it differently, take away the generator and build a list. This is what your code does in that case:

results = []
for k in range(0, n+1):
    if n % k == 0:
       results.append(k)

for factor in results:
    print factor

Now you have two loops still, but they are not nested. One is a O(n) loop to build the list, the other is a O(k) loop (with k < n) to print the results. This would still be a O(n) algorithm; constant multipliers are ignored (you'd have O(2n) -> O(n)).

All the generator does is remove the intermediary list. You don't have to first collect all the results, you get to have access to each result immediately.

Answer 2

No, this should only have time complexity O(n).

In a true nested loop, every iteration of the outer loop causes a full set of iterations of the inner loop:

for i in range(100):      # 100 times
    for j in range(i):    # i times, for *each* of the 100 values of i
         # do something

But in a generator, a yield statement causes an immediate return of control from the generator. So each time the generator is iterated only counts as one pass through the generator's loop.

So your for factor in calc_factor(100): invokes the generator once per instance of the generator's loop. So in a sense, this is the generator's loop; it's just controlled from outside the generator itself. It is therefore not an outer nested loop.