You can not win. The name=: i A. name in O(1) space and O(1) time requires severe restrictions on i . It is easy see that name=: x,name requires O(n) time if there is no extra space at the front of "name".
----- Original Message ----- From: Dan Bron <[EMAIL PROTECTED]> Date: Thursday, July 13, 2006 12:52 pm Subject: Re: [Jprogramming] special coding for stack operations > Roger wrote: > > The bar is higher for prepend/append in-place. > > OK, but since > > name=: x,name > > is logically equivalent to: > > name=: name,x O(1) space, O(1) time > name=: i A. name O(1) space, O(1) time > > for some i , then all that remains is to discover a function > foo such that: > > > name ((A.~ foo) -: (|.~ >:)) #x > > and we can have prepend-in-place in O(1) space, O(1) time. My > brief investigations have led to no obvious definition of foo . > > Here's a table of the first few required outputs of foo , where > the horizontal axis is (#name) and the vertical is (#x) : > > A.@:(|. i.)"0 table~ i. 10 > +-------------+-----------------------------------+ > |A.@:(|. i.)"0|0 1 2 3 4 5 6 7 8 9| > +-------------+-----------------------------------+ > |0 |0 0 0 0 0 0 0 0 0 0| > |1 |0 0 1 3 9 33 153 873 5913 46233| > |2 |0 0 0 4 16 64 304 1744 11824 92464| > |3 |0 0 1 0 18 90 450 2610 17730 138690| > |4 |0 0 0 3 0 96 576 3456 23616 184896| > |5 |0 0 1 4 9 0 600 4200 29400 231000| > |6 |0 0 0 0 16 33 0 4320 34560 276480| > |7 |0 0 1 3 18 64 153 0 35280 317520| > |8 |0 0 0 4 0 90 304 873 0 322560| > |9 |0 0 1 0 9 96 450 1744 5913 0| > +-------------+-----------------------------------+ ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
