{"entities":{"Q1101238":{"pageid":1111990,"ns":120,"title":"Item:Q1101238","lastrevid":42876688,"modified":"2025-07-15T15:30:47Z","type":"item","id":"Q1101238","labels":{"en":{"language":"en","value":"Upper bounds for time-space trade-offs in sorting and selection"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4047150"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101238$0895E0A9-C300-467B-A5F3-BAC6E6365895","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cd1e5053ba36db341dc1f606f402f2717da81edf","datavalue":{"value":{"text":"Upper bounds for time-space trade-offs in sorting and selection","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1101238$74FF05F6-9983-498F-B116-10F9D2360AB1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bb7cbc4227986c927b9bc09802e69bf94e704e39","datavalue":{"value":"0642.68122","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101238$258B7DFB-218C-4648-9DE5-B070FE85ED3E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ed8796dfebe118df193915d5a829c100721b8398","datavalue":{"value":"10.1016/0022-0000(87)90002-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101238$26CFF74A-7F61-40CC-A4A7-47476E26E376","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e3d27020ae42071ce34c2e2b260b922db4110865","datavalue":{"value":{"entity-type":"item","numeric-id":215688,"id":"Q215688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101238$D3A4C370-8DFB-42D8-9078-B1DCA217F4B8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101238$1C118C91-E15E-4A90-BDEE-EF07EE6A896B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1101238$28396B62-1F42-4316-A829-248B973032DD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e2123bce07c077040992a8eafadd2c3b27d8c36b","datavalue":{"value":"Upper bound time-space trade-offs are established for sorting and selection in two computational models. For machines with input in read- only random access registers, and for machines with input on a read-only tape, we present algorithms that realize trade-offs of \\(T\\cdot S=O(N^ 2)\\) for sorting and T log S\\(=O(N \\log N)\\) for selection, where S is the number of workspace registers.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101238$FC54D0C5-525C-45A6-878B-7CD0393B8BED","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101238$5C1D20D4-5440-4B69-B808-7DCFA62FB47D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101238$1706FA4D-315F-42EE-8E04-691BF9493F46","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"018dc6e507ed760ea8018c496794832f3a726993","datavalue":{"value":"4047150","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101238$411A778C-AC75-4174-9513-F130D4AE6501","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea32b2b549fd24419a857c0b59d8e23ba30ff6f8","datavalue":{"value":"time-space trade-offs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101238$9C03DAF5-977B-4245-B17C-60913763DD20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f11a697ca4320b2c5e334107aae45a37f7f8f8b","datavalue":{"value":"sorting","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101238$D1AB64BD-E145-454F-9DD3-75DECF51C97F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"54ab622f1d5d207327b01a43f7021cc5ea6aba5a","datavalue":{"value":"selection","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101238$14ACDE5C-03DA-4677-89CA-7572C027A2ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2fb06950b4b035ba153d2d29c868e5ffe67e8dee","datavalue":{"value":"computational models","type":"string"},"datatype":"string"},"type":"statement","id":"Q1101238$ED3CB665-4B5E-4B1D-A8AC-AFC403EC54B7","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101238$00D95EA7-8238-4878-8F25-80E8094E5800","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bc2e0d2db0a6d299eb21235fc0a97593259b0d3","datavalue":{"value":{"entity-type":"item","numeric-id":1394121,"id":"Q1394121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101238$12796E66-6EE9-462B-B071-99F4B7AF0D44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfda1aaef4d74a55b724a4e4b97259bc5a577f06","datavalue":{"value":{"entity-type":"item","numeric-id":3936210,"id":"Q3936210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101238$A42E9BC2-AEFA-45E7-83F7-B1B15A8D07EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1a52569f4723473b14a228edfd70f44f49aae34","datavalue":{"value":{"entity-type":"item","numeric-id":1152950,"id":"Q1152950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101238$E3B6F1BE-333D-4F77-8FBB-2388057B3994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5816339add74de89b8f86ffcede869f695aea9bb","datavalue":{"value":{"entity-type":"item","numeric-id":1143174,"id":"Q1143174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101238$500DDED4-B7B2-42E3-9684-5050FF120385","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0bc152c27af472fa9db4c1173559772bea84799","datavalue":{"value":{"entity-type":"item","numeric-id":4190139,"id":"Q4190139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101238$F00BE193-774B-480F-A687-85877A199BB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88400135b49f4397bf174ec3e94f5ee990b34d20","datavalue":{"value":{"entity-type":"item","numeric-id":1140426,"id":"Q1140426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1101238$1C9E15DF-6C8E-424E-99A1-9BF4C37837CA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"084189fe00cd303a5789eb390c51d727d247975f","datavalue":{"value":"https://doi.org/10.1016/0022-0000(87)90002-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1101238$2DFC489E-9C28-4630-916E-DF11C5D5B2A8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"68db8f055d30d5c2ab76c2cb4499f99b957f1a06","datavalue":{"value":"W2053984076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1101238$6C8D3C5E-D36C-4DA7-A284-A9BACD1F41E2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aae36d4ecd4484cf1575999828387713c4c1d7e0","datavalue":{"value":{"entity-type":"item","numeric-id":4719333,"id":"Q4719333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a7bd91fe94b97d2f36047cd6a19482a32e4b2cb","datavalue":{"value":{"amount":"+0.92857254","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101238$2FA5143E-0AA8-45D2-925B-B83506D9475B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5eff29ebbe77b8229d557da8e26ad7941ee7bd9","datavalue":{"value":{"entity-type":"item","numeric-id":3026345,"id":"Q3026345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"949ffe0d95c0f1061ce607751ac4ba928f7d2463","datavalue":{"value":{"amount":"+0.92675745","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101238$D99B9FF6-897B-4605-8A08-DEF7F028C49E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f8ca38062e02a4f77f21ef68f37a14ce15dc67e","datavalue":{"value":{"entity-type":"item","numeric-id":5054849,"id":"Q5054849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa403d11d6ac8c0b9262b29b825e49799197bf5c","datavalue":{"value":{"amount":"+0.92664224","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101238$F5D022B1-989B-4CBC-A7E4-D49FDF529F8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed479d05fa8f6681ecf555459407addd42df3de8","datavalue":{"value":{"entity-type":"item","numeric-id":2662813,"id":"Q2662813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"beb812b73a3333064709221bc9f4f6709593e626","datavalue":{"value":{"amount":"+0.9088798","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101238$B5EE71F7-49A4-4222-B5A2-766424FCC467","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c92c40dc2cdc7417b6d101a6e10dd7dd737bdaa8","datavalue":{"value":{"entity-type":"item","numeric-id":4828910,"id":"Q4828910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf763ec4ecc13a91b51713161aed27775bb1ca37","datavalue":{"value":{"amount":"+0.9060089","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101238$C1DC1301-3BAF-447E-B9E4-46667EA8CE86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d34f343eee08e1b6d91640d35d7247972a32e7c","datavalue":{"value":{"entity-type":"item","numeric-id":2930302,"id":"Q2930302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"819cdb6a6dd26e133c29752d72005ed7249135e3","datavalue":{"value":{"amount":"+0.9051339","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101238$341AA53A-BAD4-4AE1-A578-8603DF2608C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"894efda741b5b99aacb8fc88913e43ef9f304b19","datavalue":{"value":{"entity-type":"item","numeric-id":4633820,"id":"Q4633820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"819cdb6a6dd26e133c29752d72005ed7249135e3","datavalue":{"value":{"amount":"+0.9051339","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101238$5421A922-F3C2-4DDE-AB0A-AC4541A54DB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7118cc4ee41775bccd96db1f82376fa5ee1f1bd5","datavalue":{"value":{"entity-type":"item","numeric-id":799115,"id":"Q799115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec31df79036e81dd225f89c586b648313c723f2a","datavalue":{"value":{"amount":"+0.9029244","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101238$18007F25-1997-439F-A035-BADDDA28BB8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4cf54770a3d7392613305dbbcdaf4588f0957c68","datavalue":{"value":{"entity-type":"item","numeric-id":1091139,"id":"Q1091139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f1f7515da79725969b32b5d5b0c102a115f46ea","datavalue":{"value":{"amount":"+0.8893046","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101238$C1BF239C-B205-4816-B35C-5697AC0C57CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a5b1c038af6e9143c1c9fa566e894c04f46e13b","datavalue":{"value":{"entity-type":"item","numeric-id":1079376,"id":"Q1079376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f6db58e9b444c1cf524191f107cc876c9413db0","datavalue":{"value":{"amount":"+0.87884784","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1101238$BC98317E-A28B-425B-AB9E-8AE1446B67F8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1101238","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1101238"}}}}}