A Gentle Introduction to Algorithms for Web Developers

The common, self-taught web developer tinkering with their LAMP stack uses algorithms in their daily programming yet several web developers are unaware of it. When our developer realizes the importance of optimization on the web, algorithms become prevalent; however, several algorithm tutorials on the internet are meant for academics i.e. they have nasty math concepts. This tutorial is an introduction to the self-taught web developer.

Define: Algorithms

Those brilliant programmers, CLRS, that authored Introduction to Algorithms define algorithms in this simple manner:

An algorithm is thus a sequence of computational steps that transform the input into the output.

In short, an algorithm could be a simple function that takes a set of parameters as input and returns an output. They are important to understand because algorithms often determine how quickly a system runs.

For example, a database may lookup a thousand elements within a few milliseconds because certain algorithms they use run in logarithmic time.

Simple Addition Algorithm

Consider this simple addition algorithm as an example to analyze:

// Addition algorithm
function add($x, $y) {
    return $x + $y;
}

Analyzing this algorithm is straightforward. The function takes two parameters $x and $y as input and returns their sum as output. Frankly, this algorithm is simple; therefore, it’s uninteresting to us.

What we care about in algorithms is their complexity.

Complexity is also referred to as running time and growth such as the logarithmic time described for databases.

Loops Add Complexity

Some of the most important control structures to web developers are loops. Loops alone add a significant amount of complexity to algorithm; specifically, they’re usually linear complexity.

// Returns the sum of all elements in an array
function running_sum($arr) {
     $sum = 0;
     for ($i = 0; $i < sizeof($arr); $i++) {
          $sum += $i;
     }
     return $sum;
}

This algorithm has become more complex but it's still manageable for analysis. It's easy to see now that the input is an array and the output is the sum of all elements in the specified array.

Aside from input and output, we analyze algorithms based on their complexity. Complexity considers how the algorithm scales with a specific input size. In the example above, the for-loop iterates from $i to sizeof($arr); consequently, the number of iterations is one-to-one with the number of elements. We call this type of complexity linear.

Linear growth simply means that the algorithm is just a little slower than the addition algorithm because of the number of inputs considered.

Algorithms are only comparable if they share a common input and output; thus, add($x, $y) and running_sum($arr) are not comparable.

Increasing Complexity with Nested Loops

Now you must be curious about how insanely complex algorithms are made. Here's a really easy method: nest the loops.

// Prints all posts from an array of forums
function printAllPosts($forums) {
     foreach ($forums as $forum) {
          foreach ($threads as $thread) {
              foreach ($posts as $post) {
                  echo $post;
              }
          }
     }
}

We call such nested growth polynomial instead of linear. Consider each foreach-loop as a linear algorithm that processes \(f\), \(t\) and \(p\) elements respectively. By nesting our linear loops, we process \(p\) elements several times per loop such that \(f t p\) elements are processed by the end of the algorithm. Consequently, we can also call this algorithm cubic for processing \(f t p\) elements.

The trick here to analyzing algorithm complexity is counting the number of nested for-loops. Most likely, the more nesting you have, the slower your algorithm becomes; conversely, the less nesting you have, the quicker your algorithm becomes.

Therefore, when confronted with a choice between three loops or one loop for a function, it's more likely that the single loop will be quicker.

Frankly, Analyzing Algorithms is Complex

So, I will not dive into deeper details beyond the scope of analyzing nested loops. We've discovered that nested loops are a sign of slow code; however, this may not always be the case.

Considering all the cases of algorithm analysis demands comprehensive learning; consider using CLRS as a guide book to algorithms. For others, this book may be too theoretical; instead, consider practicing challenging algorithms as they appear.

Further Readings:

• Plain English explanation of Big O
• Round-Robin Scheduling Algorithm for Group Looting
• A Dynamic Programming Solution to the Josephus Problem