Linear Time Tree Traversal Generator

[Ian Kelly]

On Tue, Sep 20, 2016 at 11:03 AM, Rob Gaddi
<rgaddi at highlandtechnology.invalid> wrote:
> The only thing that's O(N log N) in that is the number of actual yield
> calls.  If you're doing pretty much anything with those values as
> they're being iterated over then they'll dominate the timing, and that
> is O(N).

It's fair to say that for sufficiently small values of N, the time
taken by the actual work will likely dominate the time taken by the
yields. It's not quite correct though to say that a O(N) piece will
dominate a O(N log N) piece, because the whole point of measuring the
asymptotic complexity is the observation that as N grows, the O(N log
N) component will *eventually* become dominant. If you're only talking
about "sufficiently small" values of N, then big O complexity is
irrelevant.

> I think there's a little bit of optimization that goes on using yield
> from.  That said, all this has a serious stink of premature
> optimization.

Agreed.