{"entities":{"Q792764":{"pageid":794612,"ns":120,"title":"Item:Q792764","lastrevid":64375884,"modified":"2026-04-11T19:26:44Z","type":"item","id":"Q792764","labels":{"en":{"language":"en","value":"Recursively rotated orders and implicit data structures: A lower bound"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3854433"}},"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":"Q792764$DA5C1009-379D-4387-AAD1-CE970B67E55F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8e812b998eb19c86bbda12f2ca58f598f04f7f52","datavalue":{"value":{"text":"Recursively rotated orders and implicit data structures: A lower bound","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q792764$2F468200-8AA4-4B38-933A-E47BFD42C636","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"05f88e9b18f50e678866c07dfa0786e81d5d01cb","datavalue":{"value":"0537.68060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792764$FF36138D-6F1B-490F-AE43-E98D666FE511","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5769598bcf9005f8ca3e876aad6c28052dfa3ccd","datavalue":{"value":"10.1016/0304-3975(84)90013-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792764$F37AC559-7C6E-464B-A99E-D341E78443AA","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":"Q792764$53044F9F-D109-4F12-A42C-F64715396DDF","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":"Q792764$9E0524B4-64CC-493C-A8B7-9A888540E23D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q792764$8F9DD9A0-859A-4DCE-B6A7-EC62E72DB833","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"00b6d49e02e2e24ebe98b057a73c668661925a7b","datavalue":{"value":"Let n values be stored in the first n locations of an array. Suppose that a dictionary is maintained on these values, so that the operations of insert, delete, and search are supported. Since no additional space is allowed, no explicit pointers can be used. Thus any information about the relationship of values must be encoded in their arrangement. Such a structure is called an implicit data structure. The paper addresses a relaxation of a sorted order, called a recursively rotated order. If the values are stored in a fashion consistent with such an order, search times of \\(O(\\log n)\\) can be achieved. The main result of the paper is that the number of data swaps for an exchange (an insertion of one element combined with a deletion of another element) for any such order is in the worst case \\(\\Omega(2^{\\sqrt{2 \\log n}}(\\log n)^{1/2}).\\) This matches to within a constant factor an upper bound on the number of data swaps.","type":"string"},"datatype":"string"},"type":"statement","id":"Q792764$D84F5C7F-A571-4BCB-B00B-91E8B5E297A5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792764$3506CAF6-0085-4F61-A603-FC107C1999A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792764$0BD6D280-DBE4-49E7-905B-16669B66C96E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792764$602EA37F-AF46-401E-B8A5-5B7E97E3A529","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5a7ef206d67a0c1684de332c130a51216b6e1f1f","datavalue":{"value":"3854433","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792764$F6A90582-74DA-4604-AC89-FD92B4A706B1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1f1814ebfb0c5873f215208cab188392d4def9a","datavalue":{"value":"lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q792764$63B696F5-2F3E-4AFA-83EA-864984C98FAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"126bc261b4ce15426bca501a6725c284417e2bf6","datavalue":{"value":"partial order","type":"string"},"datatype":"string"},"type":"statement","id":"Q792764$3D3EA645-AA20-4E24-AE6B-8B8C23E4C329","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"21d9fdbee081817f19f8fab3d793f52d8800e5f6","datavalue":{"value":"dictionary","type":"string"},"datatype":"string"},"type":"statement","id":"Q792764$999CF34F-2C7E-4824-A8D2-44E909B25E1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"130570b8c6803043a2b7fda3e631dada6d40dfea","datavalue":{"value":"implicit data structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q792764$60EC371C-CD4D-4BB5-AB9C-A6565EEBD09E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"05f14f6814778e2138d1b382af6b403fe0750201","datavalue":{"value":"recursively rotated order","type":"string"},"datatype":"string"},"type":"statement","id":"Q792764$D9ABFFC1-BBDB-48B4-8608-22712138F51A","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":"Q792764$C5870A8B-7AB4-4BD6-B897-71AB5049B618","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a31540fbf1843652d44f0a7a4e04bb5f43fbb636","datavalue":{"value":"https://doi.org/10.1016/0304-3975(84)90013-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q792764$3B0F4389-6658-4E72-939D-1A7DE42591DD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b6d83351e81606198e29b292b8d44da52a54215e","datavalue":{"value":"W2043343347","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792764$25B5BF82-78C6-41D4-9C06-B16F46BC86D8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0c8a659f7245b4a85efedb83f71c0a5e053efe1","datavalue":{"value":{"entity-type":"item","numeric-id":3962473,"id":"Q3962473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792764$02AA0F5E-9B90-4910-A155-755905EC1AE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac77c67d01c56c77a0ec7ac20ae805006fdd19bf","datavalue":{"value":{"entity-type":"item","numeric-id":1219673,"id":"Q1219673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792764$0C519725-D2B0-4FEF-B706-D1DDEB9E0F4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c4b432264b1d95c77c217a25bbd889f27e5418d","datavalue":{"value":{"entity-type":"item","numeric-id":1146004,"id":"Q1146004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792764$32BAD7C4-5F2F-4D9E-AED3-21AB037EB373","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6055ada10f353e43e3f3168e68289b3f9275dfe","datavalue":{"value":{"entity-type":"item","numeric-id":4471357,"id":"Q4471357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21fc570a6ffb10a9b81bc4625c33a90135765b3f","datavalue":{"value":{"amount":"+0.754457414150238","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":"Q792764$7FDA2E23-91A6-4D5F-9BDF-D7F990BB1058","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca3ebfd7e40581bc10de5412d9f6f5fc68517c5d","datavalue":{"value":{"entity-type":"item","numeric-id":598254,"id":"Q598254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00e2b61f85a08dc38ff1673f32d7f5a3d1b23f1a","datavalue":{"value":{"amount":"+0.7491597533226013","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":"Q792764$C09E8981-9A6C-4C5A-9182-848575785E27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a16f348fc821be1187a6d95398d750ef0494d6de","datavalue":{"value":{"entity-type":"item","numeric-id":579942,"id":"Q579942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cec01c6f31b5437a74b970b7238087d3630dbd7d","datavalue":{"value":{"amount":"+0.743645966053009","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":"Q792764$E51ED223-7C69-4AC1-93B1-4C8C694996DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9d8311c2c68d0f9312ae3c0f2eb7fbddda9a108","datavalue":{"value":{"entity-type":"item","numeric-id":2432542,"id":"Q2432542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fb737ec5477562d94e0b7a4d2735b0709cf8255","datavalue":{"value":{"amount":"+0.7340323328971863","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":"Q792764$B6BF9B41-AEDC-4203-8DDF-D6D8DF1B5A3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a20a982f3b567ce273da249f19d2d0a1d018690","datavalue":{"value":{"entity-type":"item","numeric-id":5900747,"id":"Q5900747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13855a6e03dc4860390ce86541fcfa9d4af6475e","datavalue":{"value":{"amount":"+0.7307779788970947","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":"Q792764$5BC906D5-CCC3-4B1C-8473-EA6162EFC4E8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Recursively rotated orders and implicit data structures: A lower bound","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Recursively_rotated_orders_and_implicit_data_structures:_A_lower_bound"}}}}}