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

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!

Asymptotic Analysis - Vehicles Race and Algorithm Running Time

First, watch this video:

Now, let's assume the vehicles, namely the Jet, the Car, and the Motorcycle are your algorithms.
Also, suppose the length of the racecourse is the size of the data n.

Consequently, the speed of the vehicles can be analogized to the running time of the algorithms.

Eventually, if we had to embody the circumstances of this interesting race, we will obtain this (approximately):

Supposedly, the respective vehicles speed closed-form:

Which means:

Formal Analysis:

Let the instant between 0:24 and 0:30 be represented by n0, instant 0:33 represented by n'0, and instant 0:36 by n''0.

The most interesting case to study, is Tcar(n), as it grows faster than TmotorC(n) but slower than Tjet(n).

Critique:

We notice that, if the length of the courserace was small, the motorcycle would have won this contest.

The speed of the jet is exponentially larger than both the car and the motorcycle, but we can't realize this fact only within a sufficient distance (large data).

Indeed, the motorcycle is fast at the beginning, but it gets exceeded by the jet (instant 0:33 of the video).

On the other hand, the car too, when reaching its speed apex, could overstep the motorcycle (instant 0:36 of the video), but, it was faster than the jet until the latter could transcend the former at a certain instant between 0:24 and 0:30.

We can pretend, then, that the speed of:

- the jet is exponential,
- the car is quadratic,
- the motorcycle is linear.

Also, we can assert we don't really need such a dispositive (like the one in the video) to show that a bike can be faster or slower, between a certain distance range.

But, we may image that, for instance,

Acknowledgment:

a big thank you to Dr. Naeem Nizar Sheikh, who spoke about such an example during a conversation, a couple of years ago.