Content deleted Content added
Citation bot (talk | contribs) Alter: title. Add: arxiv, doi, chapter, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | #UCB_CommandLine |
m Open access bot: doi updated in citation with #oabot. |
||
Line 40:
| title = Storing a Sparse Table with {{math|''O''(1)}} Worst Case Access Time
| volume = 31
| year = 1984| s2cid = 5399743 | doi-access = free
}}</ref> As {{harvtxt|Fredman|Komlós|Szemerédi|1984}} show, there exists a choice of the parameter {{mvar|k}} such that the sum of the lengths of the ranges for the {{mvar|n}} different values of {{math|''g''(''x'')}} is {{math|''O''(''n'')}}. Additionally, for each value of {{math|''g''(''x'')}}, there exists a linear modular function that maps the corresponding subset of {{mvar|S}} into the range associated with that value. Both {{mvar|k}}, and the second-level functions for each value of {{math|''g''(''x'')}}, can be found in [[polynomial time]] by choosing values randomly until finding one that works.<ref name="inventor"/>
| |||