August 7th, 2002, 4:10 pm
QuoteOriginally posted by: alkurInteresting approach, but doesn't O(n^(2+j)) seem scary ?Can we apply it for j>2 on PC really ?It's worse than that, actually. I had to make certain assumptions about when dividends occur to come up with O(n^{2+j}). As j approaches n, the complexity approaches O(2^n), the non-recombinant case complexity. So the answer is "not in general". I did a quick experiment using n=500 and a maturity of 1.1ynumber of divs, elapsed (s)0, 01, 12, 73, 3364, much longerMoral: It's way faster to use (1) or (2) when j is bigger than 2.