On estimating the complexity of logarithmic decomposition (Q1116321)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On estimating the complexity of logarithmic decomposition |
scientific article |
Statements
On estimating the complexity of logarithmic decomposition (English)
0 references
1988
0 references
In the theory of dynamic data structures, one frequently encounters estimates of the type \([f(n](n)=\sum_{i\geq 0}b_ if(2^ i),\) where \(...b_ 2b_ 1b_ 0\) is the binary representation of n and f is a (nondecreasing) function. We argue that `smoothness' of f, i.e., \(f(O(n))=O(f(n))\), does not play a role in estimating ``f](n), contrary to the suggestion in some references. Moreover, we give a number of useful general bounds.
0 references
dynamic data structures
0 references
binary representation
0 references
smoothness
0 references