Search code examples
algorithmlanguage-agnosticasymptotic-complexity

Exotic functions, Pochhammer and red-black trees


Consider an initially empty RB-tree, which we insert m elements into. Inserting an element takes O(log n) time, where n is the current number of elements inserted. So I can write up the total time of m insertions, as: sum log(i) for i=1..m == log(Pochhammer(1,m) ; courtesy WolframAlpha.

Indeed, the ratio of m*logm and log(Pochhammer(1,m) converges to 1, so I guess that is why I haven't seen log--Pochhammer anywhere before.

What other 'exotic' functions are in use in Computer Science? I know inverse-ackerman appears in Union-Find, etc...


Solution

  • Hypergeometric functions (which you may term "exotic") appear a lot in mathematics. The reason is that, by definition, their Taylor series have a simple form. Therefore, they appear as soon as you are using induction.

    A lot of "standard" functions are in fact hypergeometric (also, most orthogonal polynomials are). The less used ones have fancy names, but they are of the same family.

    Also here, of course, sum(log k) = log(prod k) = log k!, so you don't even need fancy stuff. The fact that you get a Pochhammer symbol probably stems from the symbolic series summation method of Mathematica. Look eg. for Zeilberger's algorithm, which sums series using hypergeometric functions.