------art_27243_16430521.1213551938993
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

On Sun, Jun 15, 2008 at 1:26 PM, Dave Thomas <dave / pragprog.com> wrote:

> How about a little cheat...
>
> vals  4, 3, 2, 1, 2]
> sum_logs  als.map {|v| Math.log(v)}.inject {|a,b| a+b}
> p vals.map {|v| Integer(Math.exp(sum_logs - Math.log(v))) }


Quite nice, and I'm more convinced that this is actually O(n) than the
original solution.  I suspect that Array#unshift is O(n) itself in most
implementations which would make for O(m) where n < m < *2,  since it's
used n times in a loop.

I think it might be O(n log n) but don't have the time right now to prove
that.

-- 
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

------art_27243_16430521.1213551938993--