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 particul...