Algorithms Orbit

Complexity theory is the field of mathematics that allows to determine the asymptotic order of growth of a given mathematical function. Let's take a look first at different possible orders of growth: We notice that n! is the most expensive order of growth in this plot; indeed, it takes a very large number of seconds, or even minutes, for instance, to execute an input of size n = 10. whilst 10n  (the cheapest order of growth) would take less than a hundred seconds to execute an input of the same size (n = 10). Moreover, we notice, for example, that 2n² is slower than 20n within the interval [0 .. 10[, but eventually do intersect when n = 10. In other words, an algorithm can be faster than an other one, when values are small, which might be misleading and deceiving. Thanks to complexity theory, determining the order of growth of any mathematical function ( remember: any algorithm can be represented as such ), helps to formally decide whether the algorithm we are goin...

We have seen previously how could represent an iterative algorithm as a mathematical function. But how are we going to do so for recursive algorithms? Let's take a look at the renowned recursive algorithm below: void hanoiTowers(int n, char left, char center, char right) { if (n == 0) { // Base Case return; } else { // General Case hanoiTowers(n - 1, left, right, center); printf("\nDisk: %d from %c to %c", n, left, center); hanoiTowers(n - 1, right, center, left); } } We notice that there are two  unconditional  recursive calls inside the  hanoiTowers() routine. I invite you to attempt to execute the following algorithm, once with n = 10 and once with n = 30 : void hanoiTowers(int n) { if (n == 0) { // Base Case return; } else { // General Case hanoiTowers(n - 1); hanoiTowers(n - 1); } } When n = 10 , this algorithm executed in...

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

First of all, it is pointless to try to study a constant time algorithm (see isFibonacci()  routine below), so we can skip this situation. For example: short isFibonacci(int number) { int value = 5 * number * number; return sqrt(value + 4) == number || sqrt(value - 4) == number; } Actually, analyses become interesting when we are to manipulate iterative algorithms and recursion. Indeed, algorithm analysis will merely help us to decide whether the solution we opted for is valid, because it is formally efficient; otherwise, we should try to persevere for extra enhancement. For my personal experience, I came to realize that I can represent a for loop mathematically using Sigma notation, especially when the loop is regular, and is additionally incremental or subtractively decremental. Ascending loop: for ( i = k ; i < n ; i += inc ) { /* * instructions */ } Can be transliterated like t...

Grasping algorithmic notions utilizing a programming language, along with data structures are enough to engage into writing impeccable computer programs and applications. With a little of experience, a thoughtful programmer would express the need to acquire an extra level of knowledge, so that s/he could assess the quality of the code s/he yields. "How can I prove this program is optimal? How can I criticize it? Can I improve it?" are all questions our talented programmer would pose. The picturesque case is the previously cited problem "The Towers of Hanoi", which we ascertained it is not easily implementable when opting for an iterative solution, whereas its recursive version is definitely easy. Further, a pproaching mathematics to "computer algorithms" would allow us to find out that "The Towers of Hanoi" recursive version is extremely expensive in both time and space. Also, a very fertile algorithm analysis area is the "sorting al...