None of these "build the list" implementations complete in linear time if you are using extended precision (or rational) numbers, because the extended precision numbers require space and time proportional to their size. It would only be linear time if the numbers themselves required constant time.
That said, apparently the linear aspect of this implementation is significant enough that it disguises the O(n^2) aspect. (Or so I have presumed from skimming over this thread -- I've not performed any benchmarks after the initial set that I posted, but they did not involve extended precision or rational arrays.) -- Raul On Sun, Dec 23, 2012 at 9:00 AM, Boyko Bantchev <boyk...@gmail.com> wrote: > In a loop-based solution, the elements of the sequence S(i) may be > computed according to the recurrence relation, but working upwards, > from S(i) to S(i+1). This guarantees completion in linear time > w.r.t. the length of the sequence. > > In an array-based solution making use of the same relation, ideally, > each S(i), i=1,…,n would be computed independently of the others, > thus repeating the same computations over and over again, and > resulting in an amount of work as large as n²/2. > > A closed formula approach may be attractive as it easily gives an > array-based solution with direct, non-incremental computation of > each item, which would seem to result in linear overall time. > However, the closed formula contains 5&^ which would not be > computed in constant time, so the overall performance would not > be linear. > > All implementations suffer an additional slowdown when extended > arithmetic is involved, but the amount of that slowdown is hard to > estimate. > > Following Roger's suggestion, I made some observations on the actual > times J takes to compute hr1x, hr2x, and la1x, depending on the length > of the sequence. hr1x and hr2x > > hr1x =: 3 : 'y(0 3+*&5)@]^:(i.@[)1 0x' > hr2x =: 3 : '(i.y)(5&(0 3+*))1 0x' > > are clearly below the seeming n²/2 time required, so the J interpreter > apparently optimizes execution by utilizing previously computed values > of S(i). However, la1x > > la1x =. 3 : '(],.3*4%~1-~])5x^i.y' > > starting from below 1000, exhibits at least a cubic behaviour: > doubling the length of the computed sequence results in a ≥8x longer > execution time. In this case, it seems that J is unable to optimize: > the powers of 5 must be computed independently of each other, and > perhaps also the verb in parentheses applies to the powers after they > are all computed first. But this is really a wild guess. > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
