Re: [gentoo-dev] HDEPEND (host dependencies for cross-compilation) for EAPI 5?

[Alexis Ballier]

On Wed, 5 Sep 2012 08:46:13 -0400
Rich Freeman <rich0@g.o> wrote:

> On Wed, Sep 5, 2012 at 7:27 AM, Ciaran McCreesh
> <ciaran.mccreesh@××××××××××.com> wrote:
> > Uhm. O(n) == O(n/2). Anything assuming they're different is just
> > wrong.
>
> We're basically debating definitions.  O notation is used to indicate
> how algorithms scale and nobody uses O(n/2) and such as a result.
>
> An algorithm that is twice as slow is still twice as slow.  That might
> or might not matter.  However,  this isn't the domain where O notation
> is used.  You use O notation when your algorithm takes 30 seconds to
> run and you want to know what happens with the dataset doubles 3000
> times.  It generally doesn't matter if the result is that it will take
> 1 trillion years to operate or 2 trillion years.  You care more about
> whether it will take minutes, hours, weeks, years, or whatever.
>
> I can't really think of any practical examples where multiplying the
> time to parse a list of maybe 50 items vs 5 lists of 10 items is going
> to make that big of a difference.  They're just lines in a text file -
> your CPU can compare a few billions characters per second.  Sure, if
> you add 75 layers of abstraction you might be able to find just the
> right point where a factor of 5 is going to make it intolerable but a
> factor of 1 is almost acceptable, but go ahead and add/remove a few
> layers and suddenly it is all fine or all horrible anyway.  That is a
> bit contrived.  That's why everybody ignores constant factors in O
> notation anyway.

ewww, t_n=O(n) means 'there exists a constant C such that t_n <= C n';
it is just nonsensical to talk about O(n) vs O(n/2): take 2C instead
of C. If you care about the constant C then dont talk about O(). Measure
it in terms of CPU cycles for example, but then it becomes dependent on
a lot of things (compiler, hardware, etc.). However, it can be proved
that (with a sane implementation) all these differences scale only by a
constant factor between two implementations; this is why, when you talk
about algorithms and not execution time on a given hardware, the O()
asymptotic estimations are the ones that make sense. O() does not say
anything about execution time, but give a good idea of how your
algorithm will scale in the future: a O(n) algorithm will be able to
process twice as much data in the same time when your hardware will be
twice as fast, a O(2^n) one will be able to process only one more.

A.