Triple Nested Loops - Two Linear Loops and One Logarithmic with a non-Constant Base - The Monster
To obtain the function that tells the exact number of iterations a set of nested loops would perform didn't seem to be a tedious exercise. However, I came accross this interesting case: - Linear outer loop - Dependent first level linear inner loop - Dependent second level logarithmic inner loop with a general base. for ( i = 1 ; i <= n ; i ++ ) { for ( j = 1; j <= i ; j ++ ) { for ( k = 1 ; k <= j ; k *= a ) { // c } } } Ceilinged/Floored logarithmic functions within summations turned out to have very lengthy closed-forms (See my previous post). We will dissect the formulas above (for any a > 1 and n >= 1): Therefore, This link points at a plain Java program that represents the above functions (f(), g () , h () , u () , v () , w () , respectively), and give the exact number of iterations performed by the covered algorithm mentioned earlier (receives two a...