Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #65886

Re: Sort one sequence by O(n) in time and O(1) in space

Show key headers only | View raw

On 02/10/2014 04:20 AM, Sturla Molden wrote:
> In general, we cannot sort a sequence in O(n) time. O(n log n) is the lower
> bound on the complexity.

Only true for sorting that involve comparison.  However, sorts that use
the values of the inputs as positional keys have a lower bound
complexity (omega) of O(n) and a worst case complexity of O(n)
and are thus asymptotically optimal.

For example, given a range of integers guaranteed to be within
the range of j to k (lower to higher), one can created a bit field
to represent all possible values of j to k.  Then, as values are
read in, the corresponding but is set true.  You have to process
the list of n elements once to read it in, and then a second
time to read them out in order.  This is a 2n operation which is O(n).

For very large ranges of j to k, this is impractical and we resort
to things like hashing functions which can perform better than
n log n sorting algorithms.  But there are lots of real world
applications where inputs-as-keys works just fine, such as short
dispatch tables in operating systems where the value to be
sorted represents a process priority, for example.

-- 
----------------------------------------------------------------------------
Tim Daneliuk     tundra@tundraware.com
PGP Key:         http://www.tundraware.com/PGP/

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Sort one sequence by O(n) in time and O(1) in space Wesley <nispray@gmail.com> - 2014-02-09 04:13 -0800
  Re: Sort one sequence by O(n) in time and O(1) in space Asaf Las <roegltd@gmail.com> - 2014-02-09 04:29 -0800
  Re: Sort one sequence by O(n) in time and O(1) in space Chris Angelico <rosuav@gmail.com> - 2014-02-09 23:39 +1100
    Re: Sort one sequence by O(n) in time and O(1) in space Wesley <nispray@gmail.com> - 2014-02-09 18:09 -0800
      Re: Sort one sequence by O(n) in time and O(1) in space Dave Angel <davea@davea.name> - 2014-02-09 22:00 -0500
  Re: Sort one sequence by O(n) in time and O(1) in space Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-09 13:41 +0000
  Re: Sort one sequence by O(n) in time and O(1) in space Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-09 14:30 +0000
  Re: Sort one sequence by O(n) in time and O(1) in space Ni Wesley <nispray@gmail.com> - 2014-02-09 22:40 +0800
  Re: Sort one sequence by O(n) in time and O(1) in space Roy Smith <roy@panix.com> - 2014-02-09 10:05 -0500
    Re: Sort one sequence by O(n) in time and O(1) in space Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-02-09 23:14 +0000
      Re: Sort one sequence by O(n) in time and O(1) in space Roy Smith <roy@panix.com> - 2014-02-09 19:15 -0500
      Re: Sort one sequence by O(n) in time and O(1) in space Wesley <nispray@gmail.com> - 2014-02-09 18:26 -0800
        Re: Sort one sequence by O(n) in time and O(1) in space Sturla Molden <sturla.molden@gmail.com> - 2014-02-10 10:20 +0000
          Re: Sort one sequence by O(n) in time and O(1) in space Steven D'Aprano <steve@pearwood.info> - 2014-02-11 05:20 +0000
            Re: Sort one sequence by O(n) in time and O(1) in space Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-02-12 11:56 +1300
          Re: Sort one sequence by O(n) in time and O(1) in space Tim Daneliuk <tundra@tundraware.com> - 2014-02-10 23:37 -0600
          Re: Sort one sequence by O(n) in time and O(1) in space Tim Daneliuk <tundra@tundraware.com> - 2014-02-10 23:37 -0600
        Re: Sort one sequence by O(n) in time and O(1) in space Chris Angelico <rosuav@gmail.com> - 2014-02-10 21:37 +1100
        Re: Sort one sequence by O(n) in time and O(1) in space Sturla Molden <sturla.molden@gmail.com> - 2014-02-10 15:03 +0000
        Re: Sort one sequence by O(n) in time and O(1) in space Chris Angelico <rosuav@gmail.com> - 2014-02-11 02:23 +1100
        Re: Sort one sequence by O(n) in time and O(1) in space Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-10 15:45 +0000
        Re: Sort one sequence by O(n) in time and O(1) in space Chris Angelico <rosuav@gmail.com> - 2014-02-11 02:52 +1100
          Re: Sort one sequence by O(n) in time and O(1) in space Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-02-11 13:19 +1300
        Re: Sort one sequence by O(n) in time and O(1) in space Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-10 16:41 +0000
  Re: Sort one sequence by O(n) in time and O(1) in space Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2014-02-09 15:48 +0000
    Re: Sort one sequence by O(n) in time and O(1) in space Wesley <nispray@gmail.com> - 2014-02-09 18:07 -0800
  Re: Sort one sequence by O(n) in time and O(1) in space Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-02-09 21:31 +0000

csiph-web