Introduction to Algorithmic Analysis

Part 00

Hey! It’s Tivadar from The Palindrome.

In today’s issue, we are starting a new series with

Alejandro Piad Morffis

, diving deep into the world of algorithmic analysis. If you are a long-time reader here, Alejandro needs no introduction: he is the author of our popular graph theory series, published a while ago.

Alejandro is one of my favorite thinkers, and I’m beyond excited to have him here once more! If you enjoy his work, make sure to subscribe to his newsletter,

The Computist Journal

.

Cheers,
Tivadar

---

Arthur is a 46-year-old blind man, who's keen on taking night strides through the park. Despite the many times his wife's told him someone would mug him, he continues to walk the park every night. One night, the unexpected happens. A soulless thug attempts to steal from Arthur, and leaves with his prized, petunia-patterned umbrella.

At the police station, the weary Detective Turing listens patiently as Arthur recounts the crime. The problem is obvious: since Arthur is blind, he never saw the culprit's face. A visual identification from a lineup is impossible. It seems hopeless.

But then, Arthur remembers a crucial detail. In the heat of the moment, while defending his floral treasure, he stomped squarely on his attacker's foot. The criminal let out a scream—a distinctive, high-pitched yelp of such a specific, glass-shattering tenor that Arthur is certain he'd recognize it anywhere.

An idea forms in Detective Turing's mind. It's unorthodox, but it just might work. He arranges a lineup of all the usual suspects, instructing a guard to walk down the line and, one by one, step on each suspect's foot. Arthur, hidden behind a one-way mirror, will listen intently for that one-of-a-kind scream.

As the procedure unfolds, suspect after suspect being stomped to a different tune—some soprano, some tenor, some baritone—Detective Turing asks himself two crucial questions. First, are we absolutely certain we will find the suspect this way? And even more importantly, is there any easier way of doing this?

Algorithmic Analysis 101

Detective Turing's questions get to the very core of algorithmic analysis, which is the formal process of evaluating an algorithm for solving a problem. It's not enough to simply have a method; we need to understand its properties. This field of study forces us to ask three fundamental questions about any given algorithm:

1. Is it correct? Does the algorithm guarantee the right answer for all possible valid inputs?

2. How much does it cost? What is the performance of the algorithm? How much time and memory will it consume as the problem gets larger?

3. Can we do better? Is there a fundamentally more efficient way to solve this problem?

In this first article in a series on algorithmic analysis, we will lay out the basic theory and techniques to answer these questions. We'll do this by focusing on the very problem Detective Turing is facing, which happens to be the simplest non-trivial problem in computer science: finding an element in an unsorted collection.

First, a quick note. While the specific problem we’ll analyze today is extremely simple, it is the basis of the most fundamental problem in computer science—searching—that powers databases, the internet, and even machine learning and AI. Understanding the basics of search (which we will tackle again and again along this series) will help us see computer science in a whole new way, and ultimately connect search to the nature of computation itself. But that’ll have to wait a bit, don’t get too impatient.

For now, let’s focus on the basics.

---

📌 The Palindrome breaks down advanced math and machine learning concepts with visuals that make everything click.

Join the premium tier to get instant access to guided tracks on graph theory, foundations of mathematics, and neural networks from scratch.

---

What is an Algorithm, Really?

Anywhere on the internet you’ll see the word "algorithm" used interchangeably with "recipe" or "procedure", which is a great starting intuition. But to analyze an algorithm formally, we need a much stricter definition. For example, a cooking recipe might say "add a pinch of salt," leaving the amount to the chef's discretion. An algorithm affords no such ambiguity.

Formally, an algorithm is a sequence of instructions written in a formal language that must have two key properties: it must always produce the correct output for any valid input, and it must terminate after a finite number of steps.

This is a stricter definition than that of a procedure, which is a sequence of steps that may fail to terminate for some inputs. If a procedure does end, it gives the right answer, but it doesn't guarantee it will always end. We will see examples of this in future articles.

To analyze an algorithm, we must execute it within a computational model. This is just an abstract machine that defines a set of allowed operations and their costs. In Detective Turing's case, the model's rules are simple: you can take one suspect at a time, stomp on their foot, and compare the resulting scream to the one Arthur remembers. These are what we call fundamental operations of the computational model.

In programming terms, this means our model only allows us to perform two operations: read the value in an arbitrary location of a list, and compare that value with another to see if they are equal. We cannot determine if one scream is "greater" or "lower" than another, nor can we "add" two screams together. We are limited to equality comparison.

It is under these strict assumptions that we must determine if we have the best algorithm. Why? Because if we change the assumptions, we change the problem. If Arthur could see—or, more pragmatically, if the values we’re searching for can be sorted—we could indeed find faster algorithms, as we will see in future articles.

Formalizing the Linear Search Algorithm

Detective Turing's foot-stomping plan is a perfect real-world algorithm. This step-by-step process is known as linear search. The code below shows how it looks in a programming language called Python. The details of the language don't matter too much; what's important is to see it as a sequence of steps that can be executed without ambiguity.

Linear search in Python. Copy the source code here!

And here is a completely different but equivalent way to visualize the linear search algorithm. This is called a flow chart and it depicts the instructions you (the computer) must follow in a graphical way. It works as you expect: take one element one at a time, compare it to your target value, and decide whether you’re done, or move on.

Now that we have formalized our algorithm, we can start analyzing it, answering the three key questions we posed in the first section: Does it work? How much does it cost? and, Can we do better?

Question 1: Does it Work?

How do we know this algorithm will always give the right answer? Intuitively, it seems obvious. By applying the test to every single suspect, you are guaranteed to either find your target or confirm they aren't in that lineup.

We can, however, prove this with mathematical certainty using a technique called proof by induction. Let's formalize our claim.

Statement P(M): After testing the first M suspects, we are certain our target is not among them (or we would have already stopped and returned True).

• Base Case (M = 1): We test the first suspect. If they aren't the one, we know for a fact our target is not in that first position. So, P(1) holds.

• Inductive Hypothesis: Let's assume P(k) is true. After testing k suspects without success, we are sure our target is not among them.

• Inductive Step: Now we test the (k + 1)-th suspect. If it's not our target, we now know two things: our target is not in the first k positions (by our hypothesis) and it's not in the (k + 1)-th position (by our new test). Therefore, we are certain the target is not among the first (k + 1) suspects, and P(k + 1) holds.

By the principle of induction, this process guarantees that if we test all N suspects without finding our target, they are simply not in the lineup. Here is a graphical illustration of the inductive idea.

So, our algorithm is correct.

By the way, in this article we use a view of algorithms that emphasizes state manipulation as the core building block of computation. Our linear search algorithm is iterative, it performs the same operations over and over, potentially changing some state (i.e., the current position we’re analyzing).

This is why a flow chart is a wonderful formalism to represent our linear search algorithm. It makes the iterative nature of the algorithm explicit.

In this iterative view of algorithms we prove correctness, as we did, by analyzing how this ever-changing state ensures that some key properties—called loop invariants—are maintained in every iteration. In this case, our loop invariant is the claim that our suspect is not among the first M positions.

In a future article we’ll see a different, dual view of algorithms as mathematical functions, which gives us recursion as the fundamental building block of computation.

One of the most beautiful ideas in computer science is how these two notions are equivalent. This is called the Church-Turing theorem, if you want to google it, but that’s a subject for another article.

Question 2: How Much Does it Cost?

So, our algorithm works. But is it any good? To answer that, we need to measure the effort it takes. There are two fundamental resources we often care about when analyzing algorithms: time and space (or memory). For now, let's focus on time, because this algorithm requires no extra space.

The time linear search takes to complete our search clearly depends on the number of suspects, N. In the worst-case scenario, your target is the very last person you test, or they aren't in the lineup at all. In either case, you have to perform N tests.

But how much is it? One millisecond per suspect? Clearly, the exact time our algorithm requires depends on way too many unspecified factors, like how fast our computer performs each of the required operations, such as comparing items and updating the current index. Every single computer will have different characteristics, so it seems impossible to give any principled analysis of running time, right?

Now, here comes the crucial point in algorithmic complexity theory. It doesn't matter how fast each operation can be performed; what we care is just the number of fundamental operations (or steps) our algorithm performs. This ties in with the notion of a computational model. The fundamental steps performed in an algorithm are precisely the fundamental operations our computational model supports.

But why lose all this detail and focus on such an abstract notion as fundamental operations? The reason is precisely because we want to analyze the algorithm itself, regardless of the computer executing it. Your computer might be faster than mine—for now, tomorrow I could buy a faster computer. By focusing on the number of fundamental steps an algorithm performs, we abstract away the hardware details and make our analysis far more general. This does, however, introduce some nuance that we will discuss later.

Now, why focus on the worst case? For starters, it gives us a guaranteed performance baseline. Our algorithm will always perform the same as or better than the worst case analysis, by definition of worst case.

Furthermore, for many algorithms—linear search included—the average-case running time happens to be asymptotically the same as the worst case—which in practice means when you compare two algorithms by worst-case, it is the same as comparing them by average-case.

Plus, the average case is often harder to analyze because it depends on averaging over all possible inputs, which might require some clever probabilities—don’t worry, we’ll also do that two articles down the road. So, while worst-case isn’t always the exact metric you want, it provides a powerful upper bound that is always useful.

To formalize this notion of worst-case upper bound, we use a mathematical tool called asymptotic notation. For our linear search, we can say its running time is bounded by a linear function on the size of the input.

We describe this upper bound using the big O notation. In this specific case, the linear search algorithm has an O(N) asymptotic complexity, meaning the running time grows linearly with the number of items. In practice, this means if you double the number of items to test, your time cost also doubles. That is, the time your algorithm takes grows at the same scale as the data you're processing.

Now, technically, our algorithm does something closer to 3N fundamental steps (for each suspect, stomp of the foot, compare the scream, move to the next suspect). But in the same sense that my computer being faster doesn’t matter, that 3x multiplier before the N doesn’t matter either.

I know, I know, trust me on this. For now, I’ll claim O(3N) is the same as O(N); we will make this notion formal in our next article.

Question 3: Can We Do Better?

Our algorithm is O(N), fine, I guess… but is that the best we can do? How do we know that some genius couldn't invent a clever algorithm that solves the problem faster? Maybe that obnoxious Detective Church two stations down the road has a better idea?

The answer is no, we can’t do it better, subject to the constraints of our computational model. We have designed the asymptotically optimal algorithm for this problem. Let’s prove it.

To prove our algorithm is optimal, we must establish a lower bound for the problem itself. That is, determining that no other algorithm ever invented, now or in the future, could solve this problem in less fundamental steps—that is, subject to the same computational model, not cheating by, e.g., making Arthur capable of seeing tomorrow.

Let's use a thought experiment to ground some intuitions first.

Imagine a malicious adversary who knows your search strategy. You claim you have a clever algorithm that can find the suspect without testing every single person. The adversary asks, "Oh really? Which spot are you going to skip?" As soon as you name the spot your algorithm won't check, the adversary places your true suspect right there. Your "clever" algorithm now fails because it missed that spot.

This suggests that to be foolproof, any algorithm must test every location in the worst case. We can formalize this with an indistinguishability argument.

Suppose you have an algorithm that claims to solve the linear search problem by checking fewer than N positions. Let’s formalize the adversary argument step by step.

1. The Unchecked Spot. First, since your algorithm checks fewer than N spots, there must be at least one spot, let's call it position i, that your algorithm never looks at.

2. Two Possible Worlds. Now, consider two different lineups that are identical in every position except for position i.

   • World A: The target suspect is at position i.

   • World B: A different person is at position i, and the target is not in the lineup at all.

3. The Algorithm's Blindness. Now your algorithm runs. Since it never tests position i, it sees the exact same sequence of suspects in both World A and World B. From its perspective, the inputs are indistinguishable.

4. The Contradiction. Because it gets the same information, your algorithm must give the same answer for both worlds. This is crucial to understand. You cannot cheat and make a choice based on data that you decided not to look at. So, your algorithm answers the same for both World A and World B.

   • If it answers "Found!" it is wrong for World B.

   • If it answers "Not Found!" it is wrong for World A.

The conclusion is inescapable: any algorithm that fails to test every position must be incorrect for at least some possible inputs. Therefore, a correct algorithm must test all N positions in the worst case.

Here is a visual representation of the core idea in the proof.

This proof establishes a lower bound on the problem itself! No matter how smart, no one can improve on Detective Turing’s idea, at least subject to the same constraints.

We formalize this using Big-Omega (Ω). The indistinguishability argument proves that searching an unsorted collection is an Ω(N) problem. And now, since our O(N) algorithm's performance matches the problem's Ω(N) lower bound, it is asymptotically optimal.

Problem solved!

Conclusion

We started with a simple problem—identifying a suspect—and built a complete framework to analyze any possible solution for it. We defined an algorithm, proved it was correct, measured its performance, and finally, proved it was the best possible among all algorithms that have to face the same constraints (that is, the same computational model).

The true power of this analysis comes from abstraction. By ignoring the specifics of the computer and instead counting fundamental operations like comparisons, we gain a universal way to measure algorithmic efficiency. This is what allows us to use tools like asymptotic notation to compare algorithms at a high level. With this lens, we can compare algorithms in abstract terms, and see for example that an O(N) algorithm is fundamentally better than an O(N²) algorithm—a notion we will explore on in next article.

Of course, this powerful abstraction comes with a trade-off. While it helps us make broad architectural decisions, it deliberately ignores real-world factors. In practice, details like CPU caches, memory access patterns, and specific hardware instructions can sometimes make a theoretically slower algorithm faster on a particular machine. Algorithmic analysis gives us the essential starting point, but practical optimization requires a deeper look at the machine itself.

But even with these practical considerations at hand, the exercise reveals a profound truth of computational complexity theory. This is where computer science stands apart from many other sciences. In many fields, like Physics, Chemistry, and Biology, our best theories are always imperfect models, destined to be replaced. There is no guarantee that the science we have today is “correct”. Everything is an approximation.

But here, in Computer Science, since our reasoning is grounded on mathematics and logic, we can often make absolute statements. Our proof that searching an unsorted list based only on comparisons is an Ω(N) problem isn't a temporary observation but a deep, immovable truth about the problem itself. No matter how advanced our technology becomes, no one will ever solve this specific problem in fewer than N comparisons in the worst case, given our assumptions.

That is a beautiful, undeniable fact of the Universe.

If you want to keep digging at the philosophical implications of computational complexity, while learning a handful of practical tools to analyze real-life algorithms, stay connected for the next entry in the series.