Does `yield from` have O(1) time complexity?

Question

Consider the following code snippet.

from typing import Iterable


def geometric_progression(
    start: float, multiplier: float, num_elements: int
) -> Iterable[float]:
    assert num_elements >= 0
    if num_elements > 0:
        yield start
        yield from geometric_progression(
            start * multiplier, multiplier, num_elements - 1
        )

This function returns the first num_elements of the geometric progression starting with start and multipliying by multiplier each time. It's easy to see that the last element will be passed through one yield-statement and num_elements-1 yield-from-statements. Does this function have O(num_elements) time complexity, or does it have O(num_elements**2) time complexity due to a "ladder" of nested yield-from-statements of depths 0, 1, 2, ..., num_elements-2, num_elements-1?

---

EDIT: I've come up with a simpler code snippet to demonstrate what I am asking.

from typing import Iterable, Any

def identity_with_nested_yield_from(depth: int, iterable: Iterable[Any]) -> Iterable[Any]:
    assert depth >= 1
    if depth == 1:
        yield from iterable
    else:
        yield from identity_with_nested_yield_from(depth-1, iterable)

Is this function O(depth + length of iterable), or is it O(depth * length of iterable)?

Skimpy

Answer 1

I could've sworn there was an optimization in place to shortcut these kinds of yield from chains, but testing shows no such optimization, and I couldn't find anything in the places I thought the optimization was implemented either.

The generators on each level of a yield from chain must be suspended and resumed individually to pass yield and send values up and down the chain. Your function has O(num_elements**2) time complexity. Also, it hits a stack overflow once the call stack reaches a depth of 1000.

Drudge

Answer 2

yield from is formally equivalent to a loop of response = yield child.send(response), plus error propagation and handling. When consumed in iteration, the response is always None and no errors are propagated/handled. This is equivalent to a for loop.

# `yield from child` without error handling/response
for x in child:
    yield x

Thus, each yield from has the time/space complexity of iterating its argument. Stacking yield from of a size n child a total of m times thus has a time complexity of O(nm).

Bhatt