From: Dave Thomas <dave@...>
Date: 2008-06-16T04:13:04+09:00
Subject: Re: little problem (google hiring puzzle)


On Jun 15, 2008, at 12:44 PM, Rick DeNatale wrote:

>> vals = [4, 3, 2, 1, 2]
>> sum_logs = vals.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 <= n*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.

Adding one extra element to vals adds:

- one more iteration to the sum loop,
- one extra call to Math.log in that loop,
- one extra iteration to the inject loop
- one extra iteration around the second map loop
- one extra call to Math.log
- one extra call to Math.exp
- one extra call to Integer

I'm guessing it's linear, but I may well be wrong.

We could memoize Math.log(v), but that would only affect running time,  
and not the order or the algorithm.