{"entities":{"Q558117":{"pageid":559884,"ns":120,"title":"Item:Q558117","lastrevid":62731800,"modified":"2026-04-11T08:05:07Z","type":"item","id":"Q558117","labels":{"en":{"language":"en","value":"Uniform distribution modulo one and binary search trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2184591"}},"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":"Q558117$8B87945A-CD45-4AE1-A929-70B85E05D142","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7d4ea9a610f7f4c568c5f37cbcc97e89882e2e5f","datavalue":{"value":{"text":"Uniform distribution modulo one and binary search trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q558117$E88585D6-7927-49AD-8896-77C96A6C0D01","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b91e43f110acfb6b01ca6a564f4a925ef0745bab","datavalue":{"value":"1075.11054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q558117$426B223E-89CA-43BD-80D8-664877AA5ACA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"97a9e04b54e3d973d1adeff47ce31775932954aa","datavalue":{"value":{"entity-type":"item","numeric-id":558116,"id":"Q558116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q558117$917996C6-5589-4FD1-9C92-89A8DDC22682","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0d2e315a33a9b42393a46d71a2f19ec5a60c3cbb","datavalue":{"value":{"entity-type":"item","numeric-id":505046,"id":"Q505046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q558117$669894CE-017E-4901-AF53-E7A70468565C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2af5fe3b27a04082f1eae9cf17090e68be06cc07","datavalue":{"value":{"entity-type":"item","numeric-id":194678,"id":"Q194678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q558117$B040ABE7-E43A-4A97-B3F8-D77E87EAC36A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3be35b99bc40d25914143aa31268a19fcdde1b9d","datavalue":{"value":{"time":"+2005-06-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q558117$CB1BCF32-B316-43BD-BFF0-AE6F767BE037","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f2d9ac350585cff73ea7ed12d7d2780f836e9452","datavalue":{"value":"http://www.numdam.org/item?id=JTNB_2002__14_2_415_0","type":"string"},"datatype":"url"},"type":"statement","id":"Q558117$A43221D3-C523-4DED-B9AB-76D47D749B36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"84109a53d9f06731d98d0040c5f414488c2fd6e6","datavalue":{"value":"https://eudml.org/doc/229169","type":"string"},"datatype":"url"},"type":"statement","id":"Q558117$D2EB3BC9-F60A-4287-BFAE-9C6D833B60A6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4e7085a59f79b51a5aa5dd344a0d062ffbd9fde4","datavalue":{"value":"Sorting a sequence \\(x=(x_k)\\) of distinct numbers from \\([0,1]\\) by Quicksort generates a binary tree. Let \\(H_n(x)\\) denote the height of the tree generated by the prefix \\(x_1,\\dots,x_n\\) of length \\(n\\) of \\(x\\). In the present paper it is shown that, if \\(x\\) is uniformly distributed in \\([0,1]\\), then \\(H_n(x)=o(n)\\) as \\(n\\to \\infty\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q558117$8AFE3CEF-DE91-4F48-80D9-E39EF38FD853","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cbf074879019e41055b4d461d7d073f58abbd088","datavalue":{"value":{"entity-type":"item","numeric-id":210450,"id":"Q210450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q558117$E708F572-1113-4EAF-9232-C058170ABAE3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f11e38b6f13ca4b029ac8b24be9156bc78adde9","datavalue":{"value":"11K06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q558117$8CE3D384-C3CD-43D7-A505-C7ABD8BB9547","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d85bd8080c61b6e59488355ff592e0c47c617bea","datavalue":{"value":"11K55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q558117$63BFA1D4-EDC9-48B3-B543-C97C9C571E10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q558117$FB6940C9-543E-409F-99DF-EACA73996787","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q558117$400BC57D-7ECD-4D5D-BA46-89BAF3C11D90","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c98cf73c2bc1698598f851949ff60b2820779907","datavalue":{"value":"2184591","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q558117$897AA330-E9EA-45C5-83FF-A612C07DC56A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15f48ed4787baedea8f978808eba84ed180892c1","datavalue":{"value":"uniform distribution","type":"string"},"datatype":"string"},"type":"statement","id":"Q558117$7CD28D9C-A11F-4B8C-9B50-CF2855DD2809","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e22f3a113575edfbd123e335487b18a37bfe2d4f","datavalue":{"value":"binary search trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q558117$80D38C0C-E23D-46DF-8E37-A1A413A6B274","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"e751138e8b150b28783c5a210048f6817120432b","datavalue":{"value":{"entity-type":"item","numeric-id":32511,"id":"Q32511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q558117$AE399DEB-6BEA-4099-BEDF-6F1016C31E6E","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":"Q558117$1C42B86A-44A5-48E9-A691-8A14E13B58B9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ffa33a8d5734b749349130a4992e17d4f50b9a71","datavalue":{"value":"W2326842096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q558117$CE690B9E-0B66-40C1-9C68-3696A14D0E03","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc5f7e7156c1f7bcfbd26ba684992778727dc47d","datavalue":{"value":{"entity-type":"item","numeric-id":3812331,"id":"Q3812331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q558117$89AA74A9-0373-4002-94E1-31FC478E8BA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0440e18bdec943de51f47ab9d02200ebb5dd8b5","datavalue":{"value":{"entity-type":"item","numeric-id":4524566,"id":"Q4524566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q558117$9D9EC8CB-35FC-46EB-BB3A-5391537B6C71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de61b1b71225c3d280912dc80b1ca0fc39f94191","datavalue":{"value":{"entity-type":"item","numeric-id":3909117,"id":"Q3909117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q558117$E65371F5-9671-46A1-A2AE-8329C2AB41AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b54e5c3679e117a5e158f211611c224fe1b587e0","datavalue":{"value":{"entity-type":"item","numeric-id":4724711,"id":"Q4724711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q558117$9D493F80-CF64-449D-848C-395D3A0EBBDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8887fee2eae8220b5bd8269701a2024ddc88680","datavalue":{"value":{"entity-type":"item","numeric-id":3990603,"id":"Q3990603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q558117$23FA4444-47A8-47A2-9120-CA388B2DE59E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d65ea504519b8a57335f60b1d2d151959cf7bcd","datavalue":{"value":{"entity-type":"item","numeric-id":4240604,"id":"Q4240604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q558117$E3F68F99-96BC-47BE-A2AC-EE56511CE2AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb1247f88c76a84b67cc8b7e0e4a397a4cdf25bc","datavalue":{"value":{"entity-type":"item","numeric-id":5904100,"id":"Q5904100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q558117$F3282BBA-B3F2-4B9A-ABDD-9E3E56BD2B6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2301db8ff12e1bfdecb2b145c77c23900b54d1b7","datavalue":{"value":{"entity-type":"item","numeric-id":4004056,"id":"Q4004056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q558117$1B6063C6-43B3-4427-BD5E-5EE847F36ACE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c580254c9c79c295f6e6e93f5fd5b85ce498cc9","datavalue":{"value":{"entity-type":"item","numeric-id":1057565,"id":"Q1057565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q558117$D65EDD22-79ED-4B3B-B6FA-9A2C70385F6F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a9deafbb48ce25e5a87a9408e5958aed3572c759","datavalue":{"value":"10.5802/JTNB.366","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q558117$FE6CB9CB-D11C-4FFF-851D-588B8F334DAA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3b0000c18f53965190ccb833f9bfdd9ff19c906","datavalue":{"value":{"entity-type":"item","numeric-id":3833634,"id":"Q3833634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d0bb2c65a47280b69556085e823a7407405e93c","datavalue":{"value":{"amount":"+0.7860508561134338","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":"Q558117$C8E81D07-C641-47D1-8965-1B97C0C04CE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"120fceafb17bf84cf601512a658e208f9518917e","datavalue":{"value":{"entity-type":"item","numeric-id":3990603,"id":"Q3990603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29ecefcae297d32cfc4dce252b98124c9383abad","datavalue":{"value":{"amount":"+0.7782812118530273","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":"Q558117$CE940DFA-75FE-4855-99E4-6396F97EC1D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1d19dadfdb8cf47ec3ce5bb012e76e8781a33e7","datavalue":{"value":{"entity-type":"item","numeric-id":1853551,"id":"Q1853551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ceac4301d931c0215b647607d9211fdde61e130","datavalue":{"value":{"amount":"+0.7777270674705505","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":"Q558117$4FBD5A2C-AF84-4E8D-97E6-C50CDF2ED886","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb8edf6b2954e50d134bfd085f3288989e6f2055","datavalue":{"value":{"entity-type":"item","numeric-id":4868264,"id":"Q4868264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0deb8368a7dbc2bddf0c7c05e6389a6299ef4151","datavalue":{"value":{"amount":"+0.7706329226493835","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":"Q558117$0327A021-1078-4389-8C9F-09D210286E5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02286c5052d858823414578f84a222499478893a","datavalue":{"value":{"entity-type":"item","numeric-id":4862790,"id":"Q4862790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cfb139f2bf86e4aca961dfbbb149dfeca0d9800e","datavalue":{"value":{"amount":"+0.7699589133262634","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":"Q558117$76228E61-C53D-4C2D-BFE3-6A44B9486F95","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Uniform distribution modulo one and binary search trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Uniform_distribution_modulo_one_and_binary_search_trees"}}}}}