Multidimensional Divide-and-Conquer and Weighted Digital Sums

Details Multidimensional Divide-and-Conquer and Weighted Digital Sums Multidimensional Divide-and-Conquer and Weighted Digital Sums

2010-02-28

arxiv.org/abs/1003.0150v1

Computer Science

Data Structures and Algorithms

44 pages, 8 figures

Scientific paper

This paper studies three types of functions arising separately in the analysis of algorithms that we analyze exactly using similar Mellin transform techniques. The first is the solution to a Multidimensional Divide-and-Conquer (MDC) recurrence that arises when solving problems on points in $d$-dimensional space. The second involves weighted digital sums. Write $n$ in its binary representation $n=(b_i b_{i-1}... b_1 b_0)_2$ and set $S_M(n) = \sum_{t=0}^i t^{\bar{M}} b_t 2^t$. We analyze the average $TS_M(n) = \frac{1}{n}\sum_{j i_2 > ... > i_k\geq 0$ and set $W_M(n) = \sum_{t=1}^k t^M 2^{i_t}$. We analyze the average $TW_M(n) = \frac{1}{n}\sum_{j

Affiliated with

Also associated with

No associations

Rating

Multidimensional Divide-and-Conquer and Weighted Digital Sums does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Multidimensional Divide-and-Conquer and Weighted Digital Sums, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multidimensional Divide-and-Conquer and Weighted Digital Sums will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-110894