Multidimensional Divide-and-Conquer and Weighted Digital Sums (Extended Abstract)∗

The Sixth Workshop on Analytic Algorithmics and Combinatorics

Y. K. CHEUNG ; Philippe FLAJOLET ; Mordecai GOLIN ; C. Y. James LEE

Others  :  http://www.siam.org/proceedings/analco/2009/anl09_009_cheungy.pdf
PID  :  18271

来源: CEUR

【 摘 要 】

This paper studies two functions arising separately in theanalysis of algorithms. The first function is the solution tothe Multidimensional Divide-And-Conquer (MDC) Recur-rence that arises when solving problems involving points ind-dimensional space. The second function concerns weighteddigital sums. Let n = (bibi−1 · · · b1b0)2 and SM (n) =∑it=0 t(t + 1)(t + 2) · · · (t + M − 1)bt2t, and set TM (n) =1