Average-Case Complexity of Shellsort (Preliminary Version) View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2002-01-18

AUTHORS

Tao Jiang , Ming Li , Paul Vitányi

ABSTRACT

We prove a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a p-pass Shellsort for any incremental sequence is Ω(pn1+1/p) for every p. The proof method is an incompressibility argument based on Kolmogorov complexity. Using similar techniques, the average-case complexity of several other sorting algorithms is analyzed. More... »

PAGES

453-462

References to SciGraph publications

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-540-66224-2
978-3-540-48523-0

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-48523-6_42

DOI

http://dx.doi.org/10.1007/3-540-48523-6_42

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1053382551


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "McMaster University", 
          "id": "https://www.grid.ac/institutes/grid.25073.33", 
          "name": [
            "Dept of Computing and Software, McMaster University, L8S 4K1, Hamilton, Ontario, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Jiang", 
        "givenName": "Tao", 
        "id": "sg:person.011617335564.48", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011617335564.48"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Waterloo", 
          "id": "https://www.grid.ac/institutes/grid.46078.3d", 
          "name": [
            "Dept of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Li", 
        "givenName": "Ming", 
        "id": "sg:person.0621576316.79", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621576316.79"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Centrum Wiskunde and Informatica", 
          "id": "https://www.grid.ac/institutes/grid.6054.7", 
          "name": [
            "CWI, Kruislaan 413, 1098, Amsterdam, SJ, The Netherlands"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vit\u00e1nyi", 
        "givenName": "Paul", 
        "id": "sg:person.014213763741.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014213763741.01"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/3-540-61680-2_42", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002391928", 
          "https://doi.org/10.1007/3-540-61680-2_42"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1214/aop/1176996798", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009269121"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/321694.321704", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013112467"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/368370.368387", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013192838"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0001-8708(77)90030-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019830529"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1025044546", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4757-2606-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025044546", 
          "https://doi.org/10.1007/978-1-4757-2606-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4757-2606-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025044546", 
          "https://doi.org/10.1007/978-1-4757-2606-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/(sici)1098-2418(199701/03)10:1/2<125::aid-rsa6>3.0.co;2-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027590546"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0196-6774(80)90003-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028591447"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0022-0000(85)90042-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046924626"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2002-01-18", 
    "datePublishedReg": "2002-01-18", 
    "description": "We prove a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a p-pass Shellsort for any incremental sequence is \u03a9(pn1+1/p) for every p. The proof method is an incompressibility argument based on Kolmogorov complexity. Using similar techniques, the average-case complexity of several other sorting algorithms is analyzed.", 
    "editor": [
      {
        "familyName": "Wiedermann", 
        "givenName": "Ji\u0159\u00ed", 
        "type": "Person"
      }, 
      {
        "familyName": "van Emde Boas", 
        "givenName": "Peter", 
        "type": "Person"
      }, 
      {
        "familyName": "Nielsen", 
        "givenName": "Mogens", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-48523-6_42", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-66224-2", 
        "978-3-540-48523-0"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "name": "Average-Case Complexity of Shellsort (Preliminary Version)", 
    "pagination": "453-462", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-48523-6_42"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "fe44a9ef3a6172468a76e7e06e27935d4cce34f6feac0860ac43e3762a815ae0"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1053382551"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-48523-6_42", 
      "https://app.dimensions.ai/details/publication/pub.1053382551"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T05:47", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000347_0000000347/records_89814_00000002.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F3-540-48523-6_42"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-48523-6_42'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-48523-6_42'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-48523-6_42'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-48523-6_42'


 

This table displays all metadata directly associated to this object as RDF triples.

126 TRIPLES      23 PREDICATES      36 URIs      19 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-48523-6_42 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Ned7a7d00a19a42dc8f73428793d95ab2
4 schema:citation sg:pub.10.1007/3-540-61680-2_42
5 sg:pub.10.1007/978-1-4757-2606-0
6 https://app.dimensions.ai/details/publication/pub.1025044546
7 https://doi.org/10.1002/(sici)1098-2418(199701/03)10:1/2<125::aid-rsa6>3.0.co;2-x
8 https://doi.org/10.1016/0001-8708(77)90030-5
9 https://doi.org/10.1016/0022-0000(85)90042-x
10 https://doi.org/10.1016/0196-6774(80)90003-6
11 https://doi.org/10.1145/321694.321704
12 https://doi.org/10.1145/368370.368387
13 https://doi.org/10.1214/aop/1176996798
14 schema:datePublished 2002-01-18
15 schema:datePublishedReg 2002-01-18
16 schema:description We prove a general lower bound on the average-case complexity of Shellsort: the average number of data-movements (and comparisons) made by a p-pass Shellsort for any incremental sequence is Ω(pn1+1/p) for every p. The proof method is an incompressibility argument based on Kolmogorov complexity. Using similar techniques, the average-case complexity of several other sorting algorithms is analyzed.
17 schema:editor Nbc151291c5134bd7b80e539f97dc59a1
18 schema:genre chapter
19 schema:inLanguage en
20 schema:isAccessibleForFree true
21 schema:isPartOf N07771b70823a476988769d4d448269f4
22 schema:name Average-Case Complexity of Shellsort (Preliminary Version)
23 schema:pagination 453-462
24 schema:productId N33c179be8f054643b322af36955af540
25 N7a71866789ae40ffb94f1f73f20ed859
26 N8e3a98c22a0346d28b630b272a21e74e
27 schema:publisher N81f6e4464d3349d89212864047fcec7c
28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053382551
29 https://doi.org/10.1007/3-540-48523-6_42
30 schema:sdDatePublished 2019-04-16T05:47
31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
32 schema:sdPublisher N37165ba561b54005b7d41f5e3ee50ec8
33 schema:url https://link.springer.com/10.1007%2F3-540-48523-6_42
34 sgo:license sg:explorer/license/
35 sgo:sdDataset chapters
36 rdf:type schema:Chapter
37 N07771b70823a476988769d4d448269f4 schema:isbn 978-3-540-48523-0
38 978-3-540-66224-2
39 schema:name Automata, Languages and Programming
40 rdf:type schema:Book
41 N0ba9fb5f06da404ba539176b00ccabb2 rdf:first N8a90e6c20c7c4b8ebb31a4ee7dde5600
42 rdf:rest N87a3eff217c94b249182d2f431717e6d
43 N11a2083d3b6c4d0fb8c542124e84b323 schema:familyName Nielsen
44 schema:givenName Mogens
45 rdf:type schema:Person
46 N2a0f277ad54c463cb3ced59883c0d033 rdf:first sg:person.014213763741.01
47 rdf:rest rdf:nil
48 N33c179be8f054643b322af36955af540 schema:name readcube_id
49 schema:value fe44a9ef3a6172468a76e7e06e27935d4cce34f6feac0860ac43e3762a815ae0
50 rdf:type schema:PropertyValue
51 N37165ba561b54005b7d41f5e3ee50ec8 schema:name Springer Nature - SN SciGraph project
52 rdf:type schema:Organization
53 N7a71866789ae40ffb94f1f73f20ed859 schema:name dimensions_id
54 schema:value pub.1053382551
55 rdf:type schema:PropertyValue
56 N81f6e4464d3349d89212864047fcec7c schema:location Berlin, Heidelberg
57 schema:name Springer Berlin Heidelberg
58 rdf:type schema:Organisation
59 N87a3eff217c94b249182d2f431717e6d rdf:first N11a2083d3b6c4d0fb8c542124e84b323
60 rdf:rest rdf:nil
61 N8a90e6c20c7c4b8ebb31a4ee7dde5600 schema:familyName van Emde Boas
62 schema:givenName Peter
63 rdf:type schema:Person
64 N8e3a98c22a0346d28b630b272a21e74e schema:name doi
65 schema:value 10.1007/3-540-48523-6_42
66 rdf:type schema:PropertyValue
67 Na7e5890c6c7b4804888274b62296e25c schema:familyName Wiedermann
68 schema:givenName Jiří
69 rdf:type schema:Person
70 Nbc151291c5134bd7b80e539f97dc59a1 rdf:first Na7e5890c6c7b4804888274b62296e25c
71 rdf:rest N0ba9fb5f06da404ba539176b00ccabb2
72 Ncb07c6e15e4545e6b8dc22e715ae0290 rdf:first sg:person.0621576316.79
73 rdf:rest N2a0f277ad54c463cb3ced59883c0d033
74 Ned7a7d00a19a42dc8f73428793d95ab2 rdf:first sg:person.011617335564.48
75 rdf:rest Ncb07c6e15e4545e6b8dc22e715ae0290
76 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
77 schema:name Information and Computing Sciences
78 rdf:type schema:DefinedTerm
79 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
80 schema:name Computation Theory and Mathematics
81 rdf:type schema:DefinedTerm
82 sg:person.011617335564.48 schema:affiliation https://www.grid.ac/institutes/grid.25073.33
83 schema:familyName Jiang
84 schema:givenName Tao
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011617335564.48
86 rdf:type schema:Person
87 sg:person.014213763741.01 schema:affiliation https://www.grid.ac/institutes/grid.6054.7
88 schema:familyName Vitányi
89 schema:givenName Paul
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014213763741.01
91 rdf:type schema:Person
92 sg:person.0621576316.79 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
93 schema:familyName Li
94 schema:givenName Ming
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621576316.79
96 rdf:type schema:Person
97 sg:pub.10.1007/3-540-61680-2_42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002391928
98 https://doi.org/10.1007/3-540-61680-2_42
99 rdf:type schema:CreativeWork
100 sg:pub.10.1007/978-1-4757-2606-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025044546
101 https://doi.org/10.1007/978-1-4757-2606-0
102 rdf:type schema:CreativeWork
103 https://app.dimensions.ai/details/publication/pub.1025044546 schema:CreativeWork
104 https://doi.org/10.1002/(sici)1098-2418(199701/03)10:1/2<125::aid-rsa6>3.0.co;2-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1027590546
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1016/0001-8708(77)90030-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019830529
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1016/0022-0000(85)90042-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1046924626
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1016/0196-6774(80)90003-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028591447
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1145/321694.321704 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013112467
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1145/368370.368387 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013192838
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1214/aop/1176996798 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009269121
117 rdf:type schema:CreativeWork
118 https://www.grid.ac/institutes/grid.25073.33 schema:alternateName McMaster University
119 schema:name Dept of Computing and Software, McMaster University, L8S 4K1, Hamilton, Ontario, Canada
120 rdf:type schema:Organization
121 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
122 schema:name Dept of Computer Science, University of Waterloo, N2L 3G1, Waterloo, Ontario, Canada
123 rdf:type schema:Organization
124 https://www.grid.ac/institutes/grid.6054.7 schema:alternateName Centrum Wiskunde and Informatica
125 schema:name CWI, Kruislaan 413, 1098, Amsterdam, SJ, The Netherlands
126 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...