From: pjb@... (Pascal J. Bourguignon)
Date: 2008-06-20T17:48:36+09:00
Subject: Re: little problem (google hiring puzzle)

yesteray <Ray.Baxter@gmail.com> writes:

> On Jun 19, 2:15�am, Ragunathan Pattabiraman
> <ragunathan.pattabira...@gmail.com> wrote:
>> > Each eval is O(n-1). You do n of them.
>>
>> I think eval I used in this case is constant time. Any other views?
>
> You are evaluating a product of n-1 terms in each eval.
>
> eval(3*2*1*2)
> eval(4*2*1*2)
> eval(4*3*1*2)
> eval(4*3*2*2)
> eval(4*3*2*1)
>
> There is no way to optimize these multiplications away.

Of course there is a way: factorize them!

eval(  3*2*1*2)
eval(4 * 2*1*2)
eval(4*3 * 1*2)
eval(4*3*2 * 2)
eval(4*3*2*1  )

You can see that there is only two multiplications going on.

-- 
__Pascal Bourguignon__