If you continue coding, sooner or later, you’re going to encounter the term algorithm.

In essence, an algorithm is a sequence of steps describing what the computer should do to solve a particular problem.

Algorithms are essential in computer science and are everywhere — even if you haven’t noticed them yet:

• Your GPS uses route-finding algorithms
• Youtube relies on audio and video compression algorithms to play high-definition videos flawlessly
• The amazing 3-D graphics in games are possible thanks to sophisticated rendering algorithms

… and the list goes on.

Computer algorithms have been developed and refined over the last couple of decades. The study of algorithms is essential to any programmer who wants to get past the basic “Hello World” beginner applications.

We can’t avoid algorithms when building complex systems that need to manage large amounts of data or solve complex problems efficiently. Besides, algorithm related questions will pop up during job interviews. So, it’s not a bad idea to know what algorithms are and how they can be applied to write more efficient code.

Algorithmic thinking is the ability to approach a problem and find the most efficient technique to solve it.

Next, I’m going to show you the difference between a simple, unoptimized example and one that relies on a battle-proven algorithm.

The Problem with Naive Implementations

To demonstrate the importance of algorithms, we’re going to solve the same problem using two different approaches.

The problem we’re about to solve is the following:

Implement a function that calculates the sum of the first N natural numbers.

All right, let’s open up VSCode* and create a new file called “sum-n.py.“

If you want to follow along with me, you should have Python 3.8+ and Visual Studio Code installed on your computer.

Declare a function called sum() which takes a single argument; this argument represents the number of natural numbers whose sum we want to calculate. The function returns an integer which gives the sum.

def sum(n: int) -> int:result = 0

The logic of our function is straightforward: it sums up all the numbers starting with zero up to the value of the input parameter n.

for i in range(n+1):result += ireturn result

Let’s try out the function:

sum_3 = sum(3)print(sum_3)

The output is 6, which is correct, since 1 + 2+ 3 = 6.

The sum() function relies on a for-in loop to calculate the sum:

for i in range(n+1):result += i

The value of n determines the number of iterations. That means that the time to execute the sum() function increases with the input parameter n. We can prove this theory by measuring the execution time.

We’re going to rely on the time Python module that provides functions to measure elapsed time.

A module is a file consisting of Python code and can include functions, classes, and variable definitions.

To use a Python module, we need to import it. Insert a new empty line at line #1 in the editor and add the following statement to import the time module:

import time

Next, insert a new line right after the sum() function’s definition. We need to call sum() with steadily increasing values for n. So, let’s define a tuple with the ranges:

ranges = (10, 1000, 10000, 100000)

Then, we call sum() in a loop with the values from the ranges tuple:

for n in ranges:sum(n)

We rely on the time.process_time_ns() function (see https://docs.python.org/3/library/time.html#time.process_time_ns) to keep track of the elapsed time. We need to sample the time before and after calling sum() to measure the time required to execute the function.

ranges = (10, 1000, 10000, 100000)for n in ranges:start = time.process_time_ns()sum(n)end = time.process_time_ns()

Finally, calculate the elapsed time and print the values:

exec_time = end — startprint(f”sum({n}) exec time: {exec_time}ns”)

Run the program. Here’s the output:

sum(10) exec time: 4000nssum(1000) exec time: 73000nssum(10000) exec time: 681000nssum(100000) exec time: 6990000ns

Your values may be slightly different, but the trend is clear: the execution time increases linearly with the input.

Next, we’re going to implement a more efficient solution using a formula that is more than 2,000 years old.

Applying a 2000-year-old Formula

The previous lecture’s code successfully computed the sum of the first N natural numbers. However, a working solution doesn’t always mean that we’ve found the optimal way to solve a particular problem. Our tests revealed that our function’s performance deteriorates as the input gets bigger.

Carl Friedrich Gauss is said to have found a better way to calculate sum(N) in his early youth. In the late 1700s, Gauss was only an elementary student. He amazed his teacher with how quickly he found the sum of the integers from 1 to 100 to be 5,050. Gauss recognized he had fifty pairs of numbers when he added the first and last number in the series, the second and second-last number in the series, and so on. That can be expressed using the following formula — known as the triangle numbers formula:

sum(N) = n * (n+1) / 2

Gauss was probably not the first to discover this formula. Likely, its origin goes back to the Pythagoreans, and it was known as early as the sixth century BC.

We can now implement an improved version of the sum() function:

def sum_optimized(n: int) -> int:return n * (n + 1) / 2

The sum_optimized() function is not just shorter, but it’s execution time doesn’t depend on the input’s size. Let’s run the same performance tests as we did for the sum() function:

sum_optimized(10) exec time: 3000nssum_optimized(1000) exec time: 2000nssum_optimized(10000) exec time: 2000nssum_optimized(100000) exec time: 2000ns

The results show that the execution times for the sum_optimized() function do not vary regardless of the input size. There are only some minor, negligible differences in the range of µs.

Besides, sum_optimized() is more efficient even for smaller values. As a reminder, here are the running times for the unoptimized sum() function:

sum(10) exec time: 4000nssum(1000) exec time: 73000nssum(10000) exec time: 681000nssum(100000) exec time: 6990000ns

sum_optimized(), unlike the sum() function, doesn’t depend on the input size.

By applying a smart, 2000-year-old formula, we managed to implement a solution with optimal performance.

Hope you’ve got a taste of what algorithms can do for your code’s elegance and speed. Finding the optimal approach requires more analysis for sure, but the results are definitely paying off.

---

This article was extracted from my book The Non-Programmer’s Programming Book: Programming Foundations for Absolute Beginners. Available on Amazon and Apple Books.