dimanche 25 mai 2014

Logarithmic Summations and Discrete Loops - Ceiling and Floor Functions

Reading the so called paper "Discrete Loops and Worst Case Performance" (by Dr. Johann Blieberger), I came across some interesting summations:

Useful here:

for ( i = 1; i <= n ; i ++ ) {
for (j = 1; j <= i ; j *= 2) {
// Some constant time C instructions.
}
}


Because:

Likewise:

Applicable here:

for ( i = 1; i <= n ; i ++ ) {
for (j = 1; j < i ; j *= 2) {
// Some constant time C instructions.
}
}


Because:

And more generally:

for ( i = 1; i <= n ; i ++ ) {
for (j = 1; j <= i ; j *= a) {
// Some constant time C instructions.
}
}


We can proceed like the following:

$\bg_white T(n) = \sum_{i = 1}^{n}(\left \lfloor \log_a(n) \right \rfloor + 1)$

Further:

for ( i = 1; i <= n ; i ++ ) {
for (j = 1; j < i ; j *= a) {
// Some constant time C instructions.
}
}


With:

Thus, while I tried to refine the results of some nested loops running time analysis, I had to face a particular summation, using both logarithm and ceiling functions, but this time, as an exponent. I finally deduced a general solution for the range [1, n]:

And similarly:

$\bg_white \\ \sum_{i = 1}^{n}a^{\left \lfloor \log_a(i) \right \rfloor} = (n - a^{\left \lfloor \log_a(i) \right \rfloor} + 1)a^{\left \lceil \log_a(i) \right \rceil} + \frac{a^{2\left \lfloor \log_a(i) \right \rfloor} - 1}{a + 1}$

I hope this was useful to you. Enjoy!