/:y and /:~y are O(n=.#y) when: - y is a boolean or character array of items with a small number of atoms - y is an array of singleton items of machine-word integers, in particular when the items are small-range machine-word integers. - y is an array of singleton items of IEEE floating point numbers
See also: http://www.jsoftware.com/jwiki/Essays/Sorting_versus_Grading ----- Original Message ----- From: Viktor Cerovski <[email protected]> Date: Wednesday, January 13, 2010 7:22 Subject: Re: [Jprogramming] Rosetta code: Merge Sort To: [email protected] > > > Raul Miller-4 wrote: > > > > On Tue, Jan 12, 2010 at 7:10 PM, Viktor Cerovski > > <[email protected]> wrote: > >> It's not always ridiculous---for example, merging two sorted > arrays of > >> total > >> length n into a sorted array merge does in O(n) while /:~ in > O(n log n). > > > > /:~ is O(n), sometimes. > > > > > True. But when? > merge is O(1) sometimes. The worst case for merge is when > merging > a single element with a sorted array. It's O(n), while > binary search will > do > it in O(log n). ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
