Linear Time Tree Traversal Generator

[Chris Angelico]

On Thu, Sep 22, 2016 at 3:32 AM, Ian Kelly <ian.g.kelly at gmail.com> wrote:
> 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.

Yeah.... but if your O(N) actual work takes fifty times as long as the
O(N log N) yields, the latter won't dominate until you have 2**50
elements, and you're unlikely to have that. I don't know exactly what
the cost of a yield is, but most definitely...

>> That said, all this has a serious stink of premature
>> optimization.
> Agreed.
... this.

ChrisA