From: yesteray <Ray.Baxter@...>
Date: 2008-06-20T06:49:51+09:00
Subject: Re: little problem (google hiring puzzle)



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.

Ray