On Algorithms 🧘🏽‍♂️

An algorithm is a formal description of the logical steps it takes to carry out a task. As programmers, we constantly use algorithms in our work to abstract away complex logic into discrete, reproducible bits of code. These abstractions form the foundation of everything we accomplish as developers; from data fetching for our user interfaces, to sorting through the mountains of data that may need to be fetched.

There are a lot of algorithms in the wild, each with their benefits and drawbacks in specific situations - so, how do we decide which algorithm will be the right tool for the job? Further, when we're writing an multiple implementations of the same function, how can we reliably determine which is "best"? For that matter, what is our vocabulary for describing the "best" case?!

Big... Oh! 🤭

If we want to generalize our code for the purposes of discussing performance and comparing its value to other bits of code, we can use Big-O (aka Bachmann–Landau or asymptotic) notation to classify algortihms according to how their running time or space requirements grow as the input size grows.

Having this vocabulary for discussing our code is invaluable for discussing the tradeoffs we make between different approaches to a problem, as well as identifying inefficiencies in our code that we can polish!

We will be primarily using Big-O notation to describe the relative efficiency of a given solution, and we'll measure that efficiency by counting the number of steps it will take for an algorithm to carry out its task.

Fun with Triangles 📐

Let's start playing with some code! For this example, we're going to practice counting the number of steps an algorithm has to take by calculating triangles (the summation of all numbers approaching n). Our first implementation will use a for-loop, like so:

const triangle = number => {
  let count = 0;
  for (let index = 0; index <= number; index++) {
    count += index;
  }
  return count;
};

triangle(5); // 15
triangle(100); // 5050

We'll also implement a short, single-line function (leveraging some of our skill in maths):

const triangle = number => (number * (number + 1)) / 2;

triangle(5); // 15
triangle(100); // 5050

Abacus Cadabacus 🧮

So which implementation here is more efficient? In order to make an educated guess, we need to start by counting all of the simple operations in each function.

Our single line algorithm only has three operations: a multiplication, an addition, and a division. This means that no matter what number you pass into it, only three steps are ever needed to get your triangle!

On the other hand, our for loop is going to take much longer to calculate a triangle at scale, and we can tell somewhat intuitively from the number of times we have to loop over a number to get to its triangle. If you were to pass in a 5, it would have to loop over the number 5 times to arrive at a triangle - if you were to pass in a million, it would take a million times! 🙈

So now it's not just one operation, but n operations; and it isn't just n additions, it's also n assignments to update the count, and another set of additions and assignments to progress through your iterator on top of that. Regardless of the exact number you pass in, the number of operations will grow proportionally with it.

A Formal Introduction 🎩

As you've now seen, Big O notation is a formalized method of 'fuzzy' counting. This methodology gives us a shared vocabulary to describe the correlation between increasing inputs with the increasing runtime of an algorithm. Details here don't matter so much - we really want to focus on trends.

Referring back to our previous examples, we could say that our slick one-liner is O(1) - the runtime is not meaningfully affected by changes to the input. On the other hand, our initial for-loop based implementation is considered to be O(n) - the number of operations in this type of algorithm is bounded by a multiple of n.

As always, you can find me on Twitter @dyyyyyyyyyl, or on Github