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:






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:




I hope this was useful to you. Enjoy!