Skip to Main content Skip to Navigation
Conference papers

Analyzing a Weighted Digital Sum Variant

Abstract : Consider the following weighted digital sum (WDS) variant: write integer $n$ as $n=2^{i_1} + 2^{i_2} + \cdots + 2^{i_k}$ with $i_1 > i_2 > \cdots > i_k \geq 0$ and set $W_M(n) := \sum_{t=1}^k t^M 2^{i_t}$. 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 $TW_M(n) := \frac{1}{n}\sum_{j \gt n} W_M(j)$. We show that $TW_M(n)$ has a solution of the form $n G_M(\lg n) + d_M \lg ^M n + \sum\limits_{d=0}^{M-1}(\lg ^d n)G_{M,d}(\lg n)$, where $d_M$ is a constant and $G_M(u), G_{M,d}(u)$'s are periodic functions with period one (given by absolutely convergent Fourier series).
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01185583
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 4:33:08 PM
Last modification on : Wednesday, August 14, 2019 - 10:46:03 AM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:03:04 AM

File

dmAM0107.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01185583, version 1

Collections

Citation

Y. K. Cheung, Mordecai Golin. Analyzing a Weighted Digital Sum Variant. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. pp.93-106. ⟨hal-01185583⟩

Share

Metrics

Record views

94

Files downloads

882