Analyzing a Weighted Digital Sum Variant
Y. K. Cheung, Mordecai Golin
Abstract
Consider the following weighted digital sum (WDS) variant: write integer n as n=2i1 + 2i2 + ⋯+ 2ik with i1 > i2 > ⋯> ik≥0 and set WM(n) := ∑t=1k tM 2it. This type of weighted digital sum arises (when M=1) in the analysis of bottom-up mergesort but is not ``smooth'' enough to permit a clean analysis. We therefore analyze its average TWM(n) := 1 / n∑j<n WM(j). We show that TWM(n) has a solution of the form n GM(≶n) + dM ≶M n + ∑d=0M-1(≶d n)GM,d(≶n), where dM is a constant and GM(u), GM,d(u)'s are periodic functions with period one (given by absolutely convergent Fourier series).
Full Text: PostScript PDF