{"entities":{"Q1118404":{"pageid":1129153,"ns":120,"title":"Item:Q1118404","lastrevid":66767976,"modified":"2026-04-12T12:43:21Z","type":"item","id":"Q1118404","labels":{"en":{"language":"en","value":"Optimal parallel selection has complexity O(log log N)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4094806"}},"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":"Q1118404$3C7ECDCB-8612-4601-8873-7E0BD3C24517","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a5c9aa2c65ef07fa0fb527f92adfb891aba57ad2","datavalue":{"value":{"text":"Optimal parallel selection has complexity O(log log N)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1118404$E2AF9F38-DE54-4A66-9C25-2C1CC5FFA57F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"23480b77d13793b76ca32d0b5603a1d1231bcf2a","datavalue":{"value":"0668.68044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118404$E03DD0E8-12AD-4276-B90B-65A2A4768A6A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9475b9d3f66d66bb065e5f71b1addb51e2869a06","datavalue":{"value":"10.1016/0022-0000(89)90035-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118404$FAA1C4C9-3A38-4E68-A088-41C52262B2A2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"494f1ab1373bf3235b5cb823eac7ac66915a0004","datavalue":{"value":{"entity-type":"item","numeric-id":190555,"id":"Q190555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118404$97DB8EFE-CBD8-477C-86DB-B09F25DA241E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0148865fab0c03358d2bdbf45e3f52d46a798048","datavalue":{"value":{"entity-type":"item","numeric-id":684397,"id":"Q684397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118404$14E57899-B6F6-403A-AFB4-E6F0F985FD41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f30d3eeaa962fa9c515f69147b2dd92e48340d2d","datavalue":{"value":{"entity-type":"item","numeric-id":603846,"id":"Q603846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118404$870ACACF-7B5C-4244-9581-7E5F8FBC54EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"11ae3d44052578af232f86664e60399b2eea5845","datavalue":{"value":{"entity-type":"item","numeric-id":6480429,"id":"Q6480429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118404$3468608F-8FC3-48E1-9F82-228DE21B01A1","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":"Q1118404$C7A9F695-7A55-481E-8D35-3EF8AA7AB52B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1118404$12B0A7F0-3384-469F-8662-E5E031905E86","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2b4032da0ff6f00d55866e4ebea246c1a470c483","datavalue":{"value":"It is shown that in the deterministic comparison model for parallel computation, \\(p=n\\) processors can select the k-th smallest item from a set of n numbers in O(log log n) parallel time. With this result all comprison tasks (selection, merging, sorting) now have upper and lower bounds of the same order in both random and deterministic models. This optimal time bound holds even if \\(p=o(n).\\)    The algorithm is based on the following combinatorial result concerning expander graphs. A graph \\(G=(V,E)\\) is a weak (A,\\(\\alpha)\\)-expander \\((\\alpha A<1)\\) if, for all \\(T\\subseteq V\\) with \\(| T| \\geq \\alpha \\cdot | V|\\), \\(| N(T)| \\geq A\\alpha | V|\\); here N(T) is the set of neighbors of vertices in T. For T,U\\(\\subseteq V\\), G is an (A,\\(\\alpha)\\)-expander from \\(T\\to U\\) if for all \\(X\\subseteq T\\) with \\(| X| \\leq \\alpha \\cdot | U|\\), \\(| N(X)\\cap U| \\geq A\\cdot | U|\\). Expander lemma: Let \\(A>B>1\\) and \\(\\alpha\\), \\(\\beta\\) be given, \\(\\alpha A<1\\), \\(\\beta B<1\\) and suppose that G is a weak (A,\\(\\alpha)\\)-expander. Then, given any large \\(U\\subseteq V\\), \\(| U| \\geq c\\cdot | V|\\) where \\(c=[1-\\alpha (A-B)]/(1-\\beta B)\\), one can find a small \\(T\\subseteq V\\), \\(| T| <\\alpha | V|\\), such that G is a (B,\\(\\beta)\\)-expander from \\(V\\setminus T\\to U\\), i.e., expansion in weak (A,\\(\\alpha)\\)-expander graphs is almost uniform. This result is of independent interest.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118404$6554D895-39CC-4728-8FB5-DE8445441383","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1833d190eb6492ca84e0c93a6ff12de5694705d3","datavalue":{"value":{"entity-type":"item","numeric-id":1109753,"id":"Q1109753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118404$C892DEEA-B7CB-42A7-9D9E-94E3ECCD13EA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118404$6C986596-0FAF-4640-98B0-63F8659C477B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118404$E137173F-284E-4319-84B5-C4EB03156A9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118404$4EA12C3B-2F13-4C43-9F91-911AD87B3B69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118404$A9802B5E-7A1E-4E35-89E0-1E6A8AD03614","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ba855a5eeb1201c36d3df4635fc91e66171a9516","datavalue":{"value":"4094806","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118404$510AC6B2-A298-47F1-B3A4-0066B13BD977","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e26a91fa3877ce4ff4e1cbc4fd7a7c11ebbd1370","datavalue":{"value":"search","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118404$95A1922C-E37F-4339-826A-04E7A3ECDE1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a63f5fdf3038af45049408a9914d671beb783a5b","datavalue":{"value":"parallel complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118404$3E8380C4-379C-4DB3-9886-BD7CDC571502","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"431ad0527b194c43bf7b26fc7f3a3705c49e72a4","datavalue":{"value":"parallel computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118404$A63B1C82-0662-4976-AF50-78BE7ED14D59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f11a697ca4320b2c5e334107aae45a37f7f8f8b","datavalue":{"value":"sorting","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118404$A68BA020-6DC9-4762-B0F9-639C1679E2ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7eb7ce57864bad79eb8b1130037c18cbe7109e9b","datavalue":{"value":"expander graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1118404$9D855BD3-1B40-4AC2-8F37-E8E90DA25328","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":"Q1118404$95F0852C-B24D-46B3-8E91-171AFC14C10A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d41c66a755d92f6210ea4ad4028350ae0c14a717","datavalue":{"value":"https://doi.org/10.1016/0022-0000(89)90035-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1118404$7A893CBF-E500-48A0-8C81-057CE69DBBF1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"159723b2634bed0cbcb52089dd84741081fa3a50","datavalue":{"value":"W2072783164","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1118404$967363A5-1EE5-47B5-936B-ACEDC39F615D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b44ed555aed1fbc544de1802074fd0df13fb2c0","datavalue":{"value":{"entity-type":"item","numeric-id":1056541,"id":"Q1056541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118404$6EF85FDD-C680-4E28-9434-687861CF2E23","rank":"normal"},{"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":"Q1118404$DCC12FC6-8F49-439C-BE70-ABA8FBFF1D5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2bd35d34c8cb4660ca6ae9b0c6b460814b14576","datavalue":{"value":{"entity-type":"item","numeric-id":1082818,"id":"Q1082818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118404$F2ADDCBC-0C21-4A4B-B91E-5C0FF9311520","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b53111e132dc19529edfdb5315df2d7ed1df8a5e","datavalue":{"value":{"entity-type":"item","numeric-id":1062763,"id":"Q1062763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118404$33CEEDDE-F3D4-4196-B460-17B425B8FAD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8c3fb0ef3c7cbeb1b19e8a3632e3bd5fcfcda10","datavalue":{"value":{"entity-type":"item","numeric-id":1165257,"id":"Q1165257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118404$9BDEB7D7-D36C-4C8F-BF92-227AFAA34DEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbebee9b3fc070c9b73e7dd9a4fe191a6564e2bd","datavalue":{"value":{"entity-type":"item","numeric-id":4071451,"id":"Q4071451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118404$AAD2BE14-ACD3-4274-959B-3C5D4FDB793E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"105a42b9d963cd1fb6e3de311b73c6eb9ace9be3","datavalue":{"value":{"entity-type":"item","numeric-id":4069777,"id":"Q4069777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1118404$294999F4-C5B6-4906-AD8E-BE52515677EE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9170e358b1f1520664b694abfd03eb0d35f3e392","datavalue":{"value":{"entity-type":"item","numeric-id":4471267,"id":"Q4471267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b8682eb953f4eaed27bca5961cf382b5d2aec24","datavalue":{"value":{"amount":"+0.8164499402046204","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118404$C73726F9-BC56-4429-ADDB-0244CBCD61FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44ac0aaaef5e2d6720838d764143ce14bcb68a42","datavalue":{"value":{"entity-type":"item","numeric-id":4962677,"id":"Q4962677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"553ddad88f22718308dab0cbf9dc61f88e28da23","datavalue":{"value":{"amount":"+0.8162597417831421","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118404$B277CA58-6080-40B4-8707-4688AF5998A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2cd7d6d33f1b21d4128a85b734193ff6f4bf773a","datavalue":{"value":{"entity-type":"item","numeric-id":1125612,"id":"Q1125612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4637d55853e894349d65c39f1db6ac9b7355c368","datavalue":{"value":{"amount":"+0.8098917007446289","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118404$2CC93816-8390-4644-B90F-A42003B29537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebc6b293612a434e7abd48ba156a0368bc59a598","datavalue":{"value":{"entity-type":"item","numeric-id":3813303,"id":"Q3813303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7975b88f6a2583f270099b9c98cc37ef2da80e44","datavalue":{"value":{"amount":"+0.8077844381332397","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118404$3DF813D5-883F-4BEE-8584-23BCCB9CF49E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f8cf907eec34cf8e62cbb5eda116001021d6169","datavalue":{"value":{"entity-type":"item","numeric-id":3359742,"id":"Q3359742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48eade9bd494f1d2520b9304c331dd5f23f4547e","datavalue":{"value":{"amount":"+0.7943331599235535","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1118404$998A4FDD-65EE-44C2-8E29-94E9EBF92B72","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Optimal parallel selection has complexity O(log log N)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Optimal_parallel_selection_has_complexity_O(log_log_N)"}}}}}