mercredi 4 décembre 2013

Delving into Algorithm Analysis - Deducing the Mathematical Representation of a Determined Study Case (II) [Iterative Algorithms and Sigma Notation]

In the precedent post, we concluded that the following code fragment:
     for (i = k; k <= n; i += inc) {
          * instructions
is equivalent to the following mathematical representation:
Let's find out what the above series is equal to (replace "instructions" by c [short of constant]).

Here, we have finally obtained the mathematical representation, the shape, or representation of the code above.

Practical case - The plainest mundane for loop:

     for (i = 1; k <= n; i ++) {
Let's manually get the exact number of instructions via the elaborated while loop
     i = 1;                // Executes 1 time
     while ( k <= n ) {    // Executes n + 1 times
         i = i + 1;        // Executes 2n times (addition and assignment)
Let's sum up: the plain mundane for loop executes 1 + (n + 1) + 2n = 3n + 2
Therefore, we can represent our for loop code fragment like the following:
T(n) = 3n + 2

and this is how its plot looks like (for any n >= 0):

Why are we doing all this? Because we need to determine the order of growth.
The order of growth is the currency by which a programmer may value whether an algorithm is expensive or "affordable". It helps to decide if the programmer should strive to come up with a better solution.
It allows to predict the algorithm's performance for small and large values (in how many nanoseconds, for instance, an algorithm is going to take to execute with 'n' values).

Be ready to get introduced to asymptotic analysis!

Aucun commentaire :

Enregistrer un commentaire