{"entities":{"Q1124333":{"pageid":1135082,"ns":120,"title":"Item:Q1124333","lastrevid":69841809,"modified":"2026-04-13T10:42:39Z","type":"item","id":"Q1124333","labels":{"en":{"language":"en","value":"Complexity of selection in \\(X+Y\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4112007"}},"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":"Q1124333$91E65C1D-8B72-4070-AC18-48204B9C7D20","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b4cb285d1e758b27a544727e1968b7f82b666151","datavalue":{"value":{"text":"Complexity of selection in \\(X+Y\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1124333$8BFA3589-EFEF-4213-BA2B-857B591CA5D2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"073011018d2e8a2f9be2d75592ce3f76786c0411","datavalue":{"value":"0678.68034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124333$09D9E2DC-E02B-4247-99D8-69412F143DCB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5ec73f0074cbdca390261e5a618ce4b9a3049c38","datavalue":{"value":"10.1016/0304-3975(89)90027-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124333$81527494-4483-461A-938E-47402D8154C6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aedf720352fcca932fab3523c4bbcafd7c4c7cdb","datavalue":{"value":{"entity-type":"item","numeric-id":1104176,"id":"Q1104176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124333$F4D0DB6F-3A3A-4DC1-92E9-7BD063943CEE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124333$EFF48B3B-8D10-47C1-A04B-FE72AE36D175","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":"Q1124333$051917B9-DEA1-4370-A635-DF525CEC5348","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dab422959a12ca09c5b85a2a2a7f73fb51e3bb75","datavalue":{"value":"The paper reviewed was inspired by the incorrect proposition by \\textit{J. Vysko\u010d} [Theor. Comput. Sci. 51, 221-227 (1987; Zbl 0642.68072)] namely that for two sorted n-vectors X and Y selecting the \\((k+1)\\)-st element of \\(A=X+Y\\) can be done in 0(log n) time if the k-th element is known. The authors show by a simple counterexample that the proof of this claim is wrong and then they prove the lower bound \\(\\Omega\\) (n) for this problem. Finally new 0(n) time algorithm for this type of selection problem is presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124333$84D175AB-8712-47A2-AC74-F9610EDA4715","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4418b7d4f2a0250db5c25bb23e561efd56a43eb7","datavalue":{"value":{"entity-type":"item","numeric-id":587571,"id":"Q587571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124333$38CAE4DB-DB2C-4211-A983-0FF47D23D3DD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124333$07F9E08E-57C3-4C13-A956-EFD384C46FCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124333$13A2D9BE-22A1-458C-A7FC-1E5F3A6FFAD9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"85bc759d6ef8648b8f0bb2d6a2a3c022cbe549be","datavalue":{"value":"4112007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124333$2EF5B067-72FF-4690-93A4-D2E932D7C8B8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1b5d370ccec49c078e4d61ff6ae7622fc1cbb55","datavalue":{"value":"complexity of selection","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124333$47EC89A6-274C-42F3-9AE9-4A099BB21FE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1f1814ebfb0c5873f215208cab188392d4def9a","datavalue":{"value":"lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124333$EF9BF665-6C30-4BB3-BE17-89784DBAF9A0","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":"Q1124333$1EF26AFF-B90B-4CAB-89E1-87841CBEDBEB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c3c5c9ff04b6f18e49b55a3aadfea507e8e9f3e4","datavalue":{"value":"https://doi.org/10.1016/0304-3975(89)90027-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1124333$44E47F5F-96E5-426E-819A-8970EEE2A6D2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"36816c92be8bca4b6055f31762feaca3b6b78468","datavalue":{"value":"W1986665918","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124333$F751FF59-EEC9-4093-BADF-97C5F9B1FE31","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"21da0e4230203025f0c9f2207dbd261e5e397085","datavalue":{"value":{"entity-type":"item","numeric-id":4060389,"id":"Q4060389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124333$257DECF9-939F-4D1D-91E7-7FC68C43FF79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63034a0e8ecf7544f06162ea0587268e73a64bf0","datavalue":{"value":{"entity-type":"item","numeric-id":4170251,"id":"Q4170251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124333$A0F365A6-FB94-49A8-8880-E461EBD00F00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcd9885056b1855f557ad76325bd57251833c73a","datavalue":{"value":{"entity-type":"item","numeric-id":4154059,"id":"Q4154059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124333$78C01747-E8EE-4666-8998-ACFA7E8F4DBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcee99c19db4a5684f00f329bafee2ecac466e27","datavalue":{"value":{"entity-type":"item","numeric-id":761793,"id":"Q761793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124333$087452FD-2D80-4089-B3A2-491C2EA1477F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"850589f2d6fd8445b18e880af09444ea210ab2b1","datavalue":{"value":{"entity-type":"item","numeric-id":761793,"id":"Q761793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6d66539c49b8373201294a84180185f2d4479ab","datavalue":{"value":{"amount":"+0.7882592082023621","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":"Q1124333$1CFF870A-E325-4CE6-BECF-5FF65C75E58B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"927f359bb472136e78498b353e3c36bd08540a9d","datavalue":{"value":{"entity-type":"item","numeric-id":911276,"id":"Q911276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae281ec678ea62748626c6fb05940a8d6804848f","datavalue":{"value":{"amount":"+0.7838122248649597","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":"Q1124333$BC9934C8-27A2-4A54-9675-26D2B09B8EEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfa822794af4c588152376245abed98f9e768d14","datavalue":{"value":{"entity-type":"item","numeric-id":3313271,"id":"Q3313271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c260dc8ebe8ce8bfeffb033a2cdd92635a66d969","datavalue":{"value":{"amount":"+0.7668634653091431","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":"Q1124333$7148D113-A9FC-4663-A73E-DCFFA3F82F26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04f5a4e08ef0619e23d605e5f7c00cdeb86d1f30","datavalue":{"value":{"entity-type":"item","numeric-id":3768394,"id":"Q3768394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10741c4d80df14396ecb3159c497f452742ebaba","datavalue":{"value":{"amount":"+0.7452262043952942","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":"Q1124333$E81985B1-7FF6-44D1-8C82-7FC0950BE479","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a349412677335128c65376327262a95bea8e367b","datavalue":{"value":{"entity-type":"item","numeric-id":798002,"id":"Q798002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"329ac48ab733df4c7ecd3224364dec28a412301f","datavalue":{"value":{"amount":"+0.7448960542678833","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":"Q1124333$D50D9B72-4867-4645-86B6-0A95B9B1846B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complexity of selection in \\(X+Y\\)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Complexity_of_selection_in_%5C(X%2BY%5C)"}}}}}