## mardi 24 juin 2014

### 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 arguments, n and a).