Article View: comp.lang.misc
Article #2213Re: Sorting bounds
From: Andrej Brodnik (Andy)
Date: Thu, 22 Nov 1990 14:28
Date: Thu, 22 Nov 1990 14:28
16 lines
1150 bytes
1150 bytes
In article <1990Nov20.202143.10746@craycos.com> jrbd@craycos.com (James Davies) writes: >The bound on sorting is O(N log N) comparisons because you must be able to >generate all of the N! possible permutations of the N inputs. ... > >... The log term may be hidden in the addressing hardware of >your memory, and may be hidden further by parallelism, but it's there. Well in a prallel version of sorting described by AKS in early 80th they took away the linear part and got O(logN) parallel time algorithm. But the problem in theis construction is an enormous constant hidden in big O. It originates from the construction of expander graphs. But I belive that the algorithm was already described in this discussion. Regards Andrej
Technical Details
Message-ID:
<1990Nov22.142850.19676@watdragon.waterloo.edu>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!watserv1!maytag!watdragon!abrodnikReferences:
<1990Nov20.202143.10746@craycos.com>Show Full Headers
Complete Article Headers
Newsgroups: comp.lang.misc Path: arc1-ca.pugleaf.net!utzoo!utgpu!watserv1!maytag!watdragon!abrodnik From: abrodnik@watdragon.waterloo.edu (Andrej Brodnik (Andy)) Subject: Re: Sorting bounds Message-ID: <1990Nov22.142850.19676@watdragon.waterloo.edu> Keywords: sorting, AKS Organization: University of Waterloo References: <1990Nov20.202143.10746@craycos.com> Date: Thu, 22 Nov 90 14:28:50 GMT Lines: 17