On estimating the complexity of logarithmic decomposition (Q1116321)

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.