Computer Algorithms

One thing I realized that many people did not know about algorithms in computer science is just how important it is, and how much the programs we use in a daily basis rely on them. Without these algorithms, computers wouldn’t even run. To start, perhaps defining “algorithm” is a good first step. When I refer to it, I’m talking not about math but of a specific pattern of writing code that achieves a goal when meeting certain criteria. That is a lot of words to say when possible, you can make things faster by being smart. But, I’d say the best way to understand this is with an example, with something called prefix sums.

The Problem

Pretend you have a list of numbers from 1 to 100, and this list is 10,000 numbers long. Your job is to find the sum of the numbers from one position to another position, which could be something like first to one thousandth numbers’ sum, or 500th to 10,000th numbers’ sum. The idea is that you would add up all numbers from the first index to the last, and that would be the output. A naïve way of doing this is to just add those numbers, say from the 500th to the 10,000th. If there is only one query (which I am defining as the sum of all numbers between 2 indexes, inclusive), meaning you only had to do this once, then sure, that is actually the fastest solution. However, what if you had a list of 500,000 queries? Worst case scenario, you’d have to add up all numbers for each query, which equals to 10,000 * 500,000 operations, or 5e9 (5 * 10^9). Simply put, while this works for small amounts of queries, it does not when you are talking about large queries which for large programs could mean millions of queries and millions of numbers. So, how do you minimize this? The way algorithms work, you are not trying to increase how fast the computer is adding numbers (though you could, that’s a whole can of worms that I won’t delve into), but how to decrease the number of operations it has to perform. There is a way to pre-process the numbers such that there is another list of the same length, but each value in the list is equal to the sum of all numbers before it. Creating this list is relatively easy, you just have to add the previous sum with the next number, and store it in code. Why this works is because the previous sum will have added the previous sum before that, and so on, so that only the first number is just itself. Now that there is this list, we can imagine that each number in this new list represents the sum of all the numbers before it. So, we know the sum from the beginning, but what if the first index isn’t the beginning, we would have to remove the sum of the numbers before the first index. To do that, we can just subtract that out from the sum of all numbers up but not including to the first index to get our answer. If you got lost in that, that’s ok, sometimes these things take time to understand, but I’ll draw out the process for you.

Below is an image of 2 lists, the top one the original, and the bottom one the prefix-summed list. Pretend that we are trying to find the sum of the second to fourth numbers, so the second, third, and fourth summed.

You can see that the second list has numbers that are equal to the sum of all numbers before that location + that location.  First, the code goes to the location of the second index in the second list, which in this case is 10, representing the sum of 1, 2, 3, and 4.

Then, since we want the sum of the second, third, and forth numbers we have to subtract all numbers before it, which in this case is just the first number, 1.

Subtracting the 1 from the 10, we get 9, which if you count is the sum of the second to fourth numbers, respectively.

That is it! But this simple change makes it so that you only have to go through all of the numbers once, at the beginning when you are creating the prefix sum, and for every query you just have to subtract 2 numbers. For computers, it is quite quick to find the number if you know its position, so this subtraction can count as one operation. That means that instead of having to do 10,000 * 500,000 operations, you only have to do 10,000 + 500,000 operations (numbers from the first example), and that makes all of the difference in the world. With sufficiently large numbers, this difference is like waiting your whole life and not getting your answers, versus a few seconds.

Side note, while this is exactly how an algorithm works, it is not really an algorithm, and more of a data type, which is that prefix summed list. This is just the best and easiest way of showing what an algorithm is to those who may not be familiar with computer science/math, which is why I chose it.

Thank you for reading, and I hope you learned something!