I was looking at my phone this morning, you know,
scrolling through this feed of news stories that
seem suspiciously tailored to exactly what I
was anxious about yesterday. And I caught myself
doing that thing we all do. I muttered, the algorithm
is out to get me today. It's become this universal
shorthand. It's the invisible hand, the ghost
in the machine, the thing we blame for, for social
media addiction or these weirdly specific ads.
But as I was prepping for this, I realized I
was using the word algorithm as a synonym for
magic or maybe conspiracy. That is the standard
operating procedure for the 21st century. It
really is. We've elevated the algorithm singular
with a capital A into this sort of digital deity.
It sees all, it knows all, and it controls our
attention. But you strip away all that Silicon
Valley mysticism, that word has a very concrete,
very rigid definition. And frankly, the reality
of what an algorithm is, and I mean the mathematical
reality, is far more interesting than the boogeyman
version we talk about. That's exactly why I wanted
to do this deep dive. I want to dismantle that
mysticism. We are going to trace this concept
from its absolute origins, which surprisingly
involve writing in mud, not coding in Python.
all the way to the bleeding edge of quantum mechanics.
It's a huge journey. It is. But I don't want
to just stay in the history books. I want to
understand the mechanics. Yeah. Because my understanding
is that an algorithm isn't just code. It's a
specific kind of logic. Precisely. If you take
nothing else away from this conversation today,
it should be this. An algorithm is not inherently
digital. It doesn't require a microchip. You
can run an algorithm with a pen and paper. Or
a pile of rocks. You can run one with a pile
of rocks. At its core, an algorithm is a tool
for solving a problem. But it's a very, very
specific type of tool. It's not just a guideline.
It's a wigger. So let's start there. If I'm a
computer scientist or a mathematician and I say
I have an algorithm for this, what am I actually
promising you? Because I feel like I use the
word loosely to mean a method, but you're saying
there's a stricter criteria. Much stricter. So
in a formal context, an algorithm is a finite
sequence of well -defined computer -implementable
instructions, typically to solve a class of problems
or to perform a computation. Okay, that's a mouthful.
Let's unpack that. Let's do it. There are a few
key words in there that carry all the weight.
The big ones are finite and well -defined. Finite
seems obvious. It has to end. You can't have
a recipe that just says stir forever. You would
think it's obvious, but in computation, it's
a profound constraint. It's not just that it
should end, it must end. An algorithm has to
proceed through a series of well -defined successive
states and eventually terminate with an output.
So an infinite loop. An infinite loop is the
classic example of what is not an algorithm.
If you write a set of instructions that get stuck
where step 10 sends you back to step 5 and step
5 sends you back to step 10 forever, that is
technically not an algorithm. It's a procedure
that fails to halt. It's a broken promise. It's
a broken promise. Exactly. An algorithm is a
contract. You give me an input, any valid input
for that class of problem, and I promise I will
perform these specific steps and I will deliver
an output. It is. Deterministic. Deterministic.
Meaning what exactly? Meaning if we both follow
the algorithm for, say, long division with the
same two numbers, we absolutely must get the
same result every time. If we don't, one of us
didn't follow the algorithm correctly. There's
no room for interpretation. OK, so that brings
up attention I found in the research. We have
this rigorous definition, deterministic, finite,
correct results. But then we look at the algorithms
running Netflix or TikTok. Those don't feel deterministic
at all. Not in the slightest. If I open my feed
today and then I refresh it a second later, I
get something different. And half the time, the
recommendation is garbage. So is that actually
an algorithm in the strict sense? This is the
crucial distinction that gets lost in the pop
culture conversation. It's probably the biggest
misconception out there. What we colloquially
call the algorithm on social media is often a
complex stack of systems, but the core decision
-making part is largely based on heuristics,
not just pure algorithms. Okay, differentiate
those for me. Algorithm versus heuristic. An
algorithm, in the pure mathematical sense, finds
the correct answer. If I ask you to sort a list
of 5 ,000 names alphabetically, there's only
one correct order. A true sorting algorithm like
merge sort or quick sort will find that exact
verifiable order every single time. It optimizes
for correctness. Okay, that makes sense. One
right answer. Right. But now let's ask a different
kind of question. If I ask a system, what is
the perfect cat video to show this listener right
now to maximize their happiness? Well, what's
the correct answer to that? There isn't one.
It's completely subjective. Exactly. Yeah. There's
no scientifically verifiable correct answer.
It's subjective. It's a moving target. And this
is where we use a heuristic. A heuristic is a
problem -solving approach that is practical.
It's a shortcut. A rule of thumb. So it's not
trying to find the perfect answer because that's
impossible. It's not. And even if it were possible,
it would be too slow. A heuristic doesn't guarantee
the optimal or perfect solution. Instead, it
provides a satisfactory solution in a reasonable
amount of time. It trades precision for speed.
So it's a guess, a highly educated, statistically
probable guess, but still a guess. It's an estimation.
I mean, think about it. If Netflix tried to calculate
the mathematically perfect show for you by analyzing
every frame of every movie ever made against
a model of every neuron in your brain, the heat
death of the universe would happen before the
video loaded. Right. That's not a great user
experience. Not at all. So instead, it uses a
heuristic. A simple one might be, this person
just watched three action movies starring Dwayne
Johnson. They'll probably like another one. It's
a shortcut that usually works. That reframes
the frustration people feel then. When the algorithm
serves you something totally bizarre, it's not
that the machine has some deep insight into your
soul and is judging you. No. It's that the heuristic
took a shortcut that didn't land. The rule of
thumb failed. Precisely. It's a rule of thumb
encoded into math. And this concept of rules
brings us to some really useful everyday analogies.
We often hear that a recipe is an algorithm.
And that's true, but only if the recipe is rigorous
enough. What do you mean? Well, a step that says
add salt to taste is not algorithmic. It requires
human judgment. It's not well -defined. But a
step that says add precisely five grams of sodium
chloride, that is algorithmic. Okay. It removes
the ambiguity. Completely. Or think about a bureaucracy.
I was thinking about this the other day. The
DMV is a massive flesh -and -blood algorithm.
That's a truly terrifying image. It is, but think
about the structure. Input. You walk in with
a specific form. Process. Go to window one. Then
there's a conditional statement. If the form
is stamped, then proceed to window two. If it
is not stamped, go to the back of the line. The
dreaded else condition. The else condition. And
it continues like that, step by step, until you
get the output. A driver's license or rejection
notice. The clerk in the window isn't supposed
to use their own judgment or creativity. They
are a processor. executing a line of code. So
if the clerk starts making exceptions, you know,
oh, you seem like a nice person. I'll let that
missing signature slide. They're essentially
introducing. bugs into the system. Or features,
depending on if the exception benefits you. But
yes, exactly. The whole system relies on the
rigidity of the steps. And this need for rigid,
repeatable steps is ancient. It predates computers
by thousands of years. We tend to think this
all started with Alan Turing or, you know, Bill
Gates. But the history of the algorithm is really
the history of civilization trying to organize
itself. Let's go back to that origin, because
the word itself, algorithm. It feels very foreign.
It has that al - prefix, like algebra. Which
is a dead giveaway of its Arabic origins. The
etymology is actually a fascinating story of
a game of telephone played across centuries and
languages. We need to go back to the 9th century,
to the House of Wisdom in Baghdad. The intellectual
center of the world at the time. Absolutely.
This was the hub of science, math, and philosophy.
And there was a Persian scholar there named Mu'mat
ibn Musa al -Khwarizmi. Al -Khwarizmi. And if
you say that fast enough... Yeah, it takes a
few centuries of mangling to get there. Al -Khwarizmi
was a polymath, a true genius. He wrote a groundbreaking
book around 825 AD. In Arabic, the title was
something like Kitab al -Asab al -Hindi, which
translates to the Book of Indian Computation.
Indian computation? Yes. He was essentially introducing
and synthesizing the Hindu -Arabic numeral system,
our number 0, 1, 2, 3, and so on to the Islamic
world. And from there, it was eventually transmitted
to Europe. So before this, Europe is stuck using
Roman numerals. Yes. And just try doing long
division with Roman numerals. It's an absolute
nightmare. How do you divide CXA3 by 9X? It doesn't
work well at all. Alex Goresmy's book laid out
the step -by -step procedures for how to add,
subtract, multiply, and divide using the decimal
system and place values. It was revolutionary.
So he wrote the algorithm for doing arithmetic.
He wrote the book on it. When his works were
translated into Latin in the 12th century, the
translators were faced with his name, Alcorismi.
They didn't know what to do with it, so they
just Latinized it. It became Algorismus. So Algorism
originally just meant doing math with decimals,
the new way. Exactly. Algorism was the name of
the newfangled method of calculation. It was
contrasted with the old way. Using an abacus.
But then fast forward a few hundred years to
the 15th century, European scholars are rediscovering
classical Greek texts. Right. They look at this
word algorithm and they mistakenly confuse it
with the Greek word arithmos, which means number.
It's the root of our word arithmetic. They thought
it had a Greek root that it didn't actually have.
Right. They thought it was a spelling error.
So they corrected it. They changed the es in
algorithm to a phi to make it look more Greek.
And so algorithm became algorithm. It was essentially
a typo that stuck. I love that. The very word
for a precise, rigid set of instructions comes
from a sloppy translation error. The irony is
pretty thick, isn't it? But while the name comes
from the 9th century, the actual practice is
much, much older. If we define an algorithm as
a step -by -step procedure to solve a problem,
We can find them written in cuneiform on clay
tablets in ancient Mesopotamia, dating back to
around 2500 BC. This is the Sumerian stuff. Yes.
Archaeologists unearthed these tablets near Baghdad,
and they are, for all intents and purposes, textbooks.
They lay out procedures for division and for
calculating compound interest for loans. So even
back then, algorithms were about money. Some
things never change. But they didn't have algebraic
symbols like X or Y. They wrote it out in prose,
like a recipe. Take the number, find its reciprocal,
multiply by the dividend. It's a script for a
human computer to follow. And the Babylonians
took this further with astronomy, right? I read
they were incredible record keepers. The Babylonians
were obsessed with predicting the future, both
for religious and agricultural reasons. Where
will the planet Jupiter be next month? When is
the next solar eclipse? You can't just eyeball
that. You need a rigorous calculation. And they
developed algorithms for that. They did. They
developed incredibly sophisticated algorithms
to track and predict planetary motion, all using
a base -60 number system. Which is why we still
have 60 seconds in a minute. 60 minutes in an
hour and 360 degrees in a circle. We are running
Babylonian legacy code. We absolutely are. It's
baked into our daily lives. And the Egyptians
were doing the same. The Rhine Mathematical Papyrus,
which dates to around 1550 BC, is basically a
textbook of algorithms for architects and scribes.
It has step -by -step guides on how to calculate
the slope of a pyramid or how to fairly divide
loaves of bread among workers. Practical problems.
Very practical. It's all about process. And that
brings us to the Greeks. Who really formalized
the idea of mathematical proof and logic? There's
one ancient algorithm I bet you remember learning
in school. It's probably the only one that gets
taught by name in a non -computer science class.
The sieve of Eratosthenes. The sieve, yes, for
finding prime numbers. Exactly. And it's such
a beautiful, elegant, tactile algorithm. It's
a perfect example of how an algorithm differs
from just randomly looking for something. Walk
us through it because the process is the whole
point. Okay, so imagine you have a big scroll
and you list out all the numbers from 1 to, say,
100. You want to find all the prime numbers in
that list. The brute force way would be to look
at each number individually. is 91 prime. Let
me try dividing it by 2, then by 3, by 4, by
5. That's incredibly slow and error -prone. Eratosthenes,
a Greek mathematician around 200 BC, came up
with a much smarter process, an algorithm. Start
with the first prime, 2. Circle it. Now go through
your entire list and cross out every multiple
of 2. So 4, 6, 8, 10, all the way to 100. They're
all gone. You've eliminated half the numbers
in one pass. Pretty much. Step two, find the
very next number on your list that isn't crossed
out. That number is three. Circle it. It must
be prime. Now go through the list and cross out
every multiple of three. So six is already gone,
but nine, 15, 21, you cross them out. And you
just keep repeating that same instruction. Find
the next available number, circle it, then eliminate
all its multiples. You just keep turning the
crank. The next number is five. circle it, cross
out its multiples, then seven. And you keep going.
When you finish, every single number that is
left, the ones that haven't been crossed out,
must be prime. You don't have to check them individually.
The process guarantees the result. That's the
key. It's the elimination of guesswork and redundant
work. It's the triumph of process over brute
force. And speaking of eliminating guesswork,
we have to mention another giant from that Islamic
golden age. We talked about al -Kharizmi, but
we have to talk about al -Kindi. He was working
around the same time also in Baghdad. This is
the code breaker. The father of cryptanalysis.
Before Al -Kindi, if you intercepted a secret
message where every letter was substituted for
another, a simple cipher, you just had to guess.
It was pure trial and error. Root force again.
Right. But Al -Kindi, who was also a musician
and an optician and a philosopher, had a key
insight. He noticed a pattern in language itself.
He realized that in any given language, some
letters appear far more often than others. In
English, for instance, E's is everywhere. Z is
very rare. Frequency analysis. He invented it.
He turned that observation into a rule, an algorithm
for breaking codes. Step one, get a long, unencrypted
text in the target language and count the frequency
of every letter. E appears about 12 % of the
time, T about 9%, and so on. Make a table. Step
two. Take the secret encrypted message and count
the frequency of every symbol in it. Step three.
Assume the most common symbol in the secret message
corresponds to the most common letter in the
language. So you swap it with E. Then swap the
second most common symbol with T. You keep doing
that. And the message starts to reveal itself.
It starts to become readable. He turned code
breaking from a mystical art into a statistical
science. A repeatable process. This brings us
to a really interesting pivot point in the story.
All of these examples. Sumerian division, the
Greek sieve, Arab code breaking. They were all
algorithms designed to be run by humans. The
computer was a person with a stylus or a quill
pen. Yes, the wetware. Exactly. But at some point,
we decided we wanted to outsource the labor.
We wanted to mechanize the process of thinking.
The mechanization of the algorithm. This is the
industrial revolution of thought. And oddly enough,
the conceptual bridge isn't a calculator. It's
the clock. The clock. How so? Think about the
verge escapement mechanism in a weight -driven
mechanical clock from the Middle Ages. That tick
-tock sound. That is the sound of a machine controlling
the release of energy in discrete, quantized
packets. It is a machine that follows a rigid,
unthinking rule set to divide the continuous
flow of time into identical units. Okay, I see
that. It's automation. It's automation. And it
inspired the idea of automata. These intricate
machines and clockwork figures that could move
by themselves according to a preset program.
This planted the seed of an idea. If we can make
a machine follow rules to move, can we make one
follow rules to think? And this leads us to the
19th century and the two people who I think are
the most fascinating what -if story in the history
of technology, Charles Babbage and Ada Lovelace.
The tragedy of Babbage and Lovelace is that they
were living in 1840, but they were thinking in
1940. They were a century ahead of their time.
So tell us about Babbage. Charles Babbage was
a brilliant but famously grumpy English mathematician.
He was frustrated by the errors he found in hand
-calculated mathematical tables, like logarithm
tables. These were full of mistakes made by the
human computers who compiled them, so he set
out to build a machine to do it perfectly. His
first design was the difference engine. The one
we really care about is the second one, the analytical
engine. Yes. The analytical engine was a massive
leap forward. It wasn't just a special purpose
calculator like the difference engine. Because
calculators already existed in some form, Pascal
had built one in the 1600s. Right. So what made
the analytical engine different? It was designed
to be a general purpose computer. It had all
the fundamental components of a modern computer
just built out of brass gears and steam power.
It had a store, what we would call memory or
RAM. It had a mill, what we would call the central
processing unit or CPU. And it took its instructions
from punch cards. Yes. He borrowed the idea from
the jacquard loom. which used punch cards to
control the patterns in woven fabrics. A hole
in the card meant one thing, no hole meant another.
Babbage realized he could use this to feed not
just data, but instructions into his machine.
But he never actually built it. He never fully
built it. He was a perfectionist. He kept changing
the design. He ran out of funding from the British
government. And he alienated most of his machinists.
It was this incredible, sprawling brass and scheme
monster that existed almost entirely on paper.
And this is where Ada Lovelace comes in. This
is where Ada Lovelace, the daughter of the poet
Lord Byron, enters the story. She was a gifted
mathematician, which was rare for a woman of
her era. She met Babbage, saw his plans, and
understood them perhaps better than he did. She
saw something he had missed. What was that? Babbage
saw his machine as a super calculator, a number
cruncher. Lovely saw its potential as a symbol
manipulator. She realized that the numbers in
the machine didn't have to just represent quantities.
This is that famous quote I have in the notes.
She wrote that the engine might... compose elaborate
and scientific pieces of music of any degree
of complexity or extent. That is the conceptual
moment the modern computer is born. That's the
leap. She understood that a number in a gear
could represent a musical note. It could represent
a letter of the alphabet, a logical state, a
pixel. If you can write an algorithm to manipulate
numbers, you can write an algorithm to manipulate
any kind of symbol. You can compute reality.
And to prove it, she wrote the first program
for this theoretical machine. She did. She translated
a paper about the analytical engine, and in her
own notes on the translation, which were three
times longer than the original paper, she included
a detailed step -by -step algorithm to calculate
a complex sequence of numbers called the Bernoulli
numbers. And that's considered the first piece
of computer software. It is widely cited as the
first algorithm specifically designed to be executed
by a machine, written a full century before the
first electronic general purpose computer, ENIAC,
was built. She is rightly considered the world's
first programmer. But since the machine wasn't
built, the theory kind of went dormant for a
while. It was this fascinating dead end until
the 20th century. And then we get Alan Turing.
Turing, the man who formalized everything. In
1936, he published a paper that is arguably the
most important single document in the history
of computer science on computable numbers. And
he wasn't trying to build a computer. He was
trying to solve a logic puzzle. He was. It was
a famous problem posed by the mathematician David
Hilbert called the Entscheidungsproblem, the
decision problem. The question was, essentially,
is there an algorithm that can take any logical
statement and determine, yes or no, whether that
statement is universally valid? Sort of a truth
machine. A universal truth machine. To answer
this question, Turing had to first define what
an algorithm or a method of computation actually
was. And to do that, he invented a thought experiment.
The Turing machine. Now, again, this isn't a
physical machine you can go out and buy at Best
Buy. No, it's a mathematical model of computation.
It's the simplest possible computer you can imagine.
Imagine an infinitely long tape of paper divided
into squares, like a roll of toilet paper. And
there's a little box, the head. that sits over
one square at a time. This head can do only three
things. It can read the symbol on the square,
it can write a new symbol on the square, and
it can move one square to the left or one square
to the right. That's it. Read, write, move. That's
it. And it has a little book of rules, a state
table, that tells it what to do. For example,
a rule might say... If you are in state four
and you read a one, write a one, move to the
right and change to state six. It sounds incredibly
simple, almost too simple. That's the genius
of it, because Turing proved that this incredibly
simple mechanism can perform any computation
that is possible to perform. If an algorithm
exists to solve a problem. Turing machine can
run it. This is the universal Turing machine.
Exactly. Your iPhone, a supercomputer at NASA,
they're just very, very fast, very small, very
fancy Turing machines. They don't do anything
fundamentally different from read, write, and
move based on a set of rules. This is the theoretical
basis of all modern computing. But Turing also
proved something devastating with this model.
He did. By defining what was computable, he could
also prove that there are some problems that
are uncomputable, problems for which no algorithm
can ever exist. This is the halting problem,
right? The famous halting problem. In simple
terms, the question is this. Can you write a
program, let's call it program H, that can analyze
any other program and its input and tell you
with 100 % certainty if that other program will
eventually finish, that is, halt. Or if it will
get stuck in an infinite loop and run forever?
And the answer is? The answer is a resounding
no. It is logically impossible. He proved it
with a beautiful contradiction. You can't write
a general purpose algorithm that can perfectly
predict the behavior of all other algorithms.
This means there are hard fundamental limits
to what computation can ever achieve. We can't
solve everything. That is a humbling thought.
We built these machines to be these perfect logical
engines. And right at their theoretical foundation,
there's a giant sign that says, here be dragons.
Or some problems are unsolvable. Exactly. But
for the problems we can solve, the next logical
question is, well, how efficiently can we solve
them? Because as we moved from Babbage's gears
to vacuum tubes to silicon chips, we quickly
realized that not all algorithms are created
equal. Some are incredibly fast. Some are agonizingly,
unusably slow. And this is where we get into
algorithmic analysis. This is the stuff that
makes first -year computer science students sweat.
The dreaded big O notation. Right. Let's try
to demystify this. The key idea, as I understand
it, is that we don't measure an algorithm's speed
in seconds, right? Because a supercomputer from
2024 is obviously going to be faster than a desktop
from 1994. Correct. Measuring in seconds is useless
because hardware keeps getting faster. So instead,
we measure an algorithm's efficiency in terms
of its growth rate. How many steps or operations
does the algorithm take relative to the size
of the input? We use the letter N to represent
the size of the input. Okay, N. So if I'm sorting
a deck of playing cards, N is 52. If I'm sorting
the phone book for New York City, N is, what,
8 million? Exactly. And big O notation describes
how the number of operations grows as N gets
bigger. Let's start with the best case scenario.
This is called O1, or constant time. Constant
time. This means that no matter how big N is,
the task always takes the same amount of time.
It takes just one step. An example would be,
give me the first name on a list. Whether that
list has 10 names or 10 billion names, grabbing
the very first one is a single operation. That's
the dream. Instant access, regardless of scale.
It is. The next level up is ON, or linear time.
This is the most intuitive one. This is our brute
force search. If I ask you, is the name Waldo
in this unorganized pile of 100 papers? You have
to look at every single paper one by one. You
might get lucky and find them on the first try.
You might. That's the best case. But we care
about the worst case. In the worst case, Waldo
is on the very last paper or not there at all.
So if you have 100 papers and 100 could take
you 100 steps. If you have a million papers,
it could take a million steps. The work grows
in a straight line equally with the data. It's
manageable for small tasks, but it doesn't scale
well if you have truly big data. Not at all.
And this is why the next level up is where the
real magic of computer science. happens. This
is O log on or logarithmic time. This is the
phone book analogy. The classic phone book analogy.
It perfectly illustrates the power of an algorithm
called binary search. So imagine the phone book
again with its millions of names. But this time,
critically, it's sorted alphabetically. You're
looking for Smith. You don't start at A and read
every name. That would be O -N. Well, you open
it roughly to the middle. You open it to the
middle. You see names starting with M. You know,
Smith comes after M. So you can take the entire
first half of the book from A to M and throw
it away. You just deleted half the problem in
a single step. In one step. Then you take the
remaining half from M to Z and you cut that in
half. You land on R. Still not there. Smith is
after R. So you throw away the M to R section.
You keep splitting the problem in half again
and again. So how much faster is that, really?
It's astronomically faster. Let's use that phone
book of, say, one million names. A linear search,
O in the worst case, takes one million steps.
A binary search, O log N, takes about 20 steps.
Wait, only 20. From a million down to 20? That's
the power of logarithms. Two to the power of
20 is roughly a million. You only need to cut
the deck 20 times to find one specific card in
a deck of a million. This is what makes searching
massive databases possible. This is the power
of a good algorithm. It turns an impossible task
into a trivial one. But then, then there's the
dark side. The bad algorithms. The ones that
cause systems to grind to a halt. Oh, yes. The
ones to be avoided at all costs. Yes. The next
step up is O -N or quadratic time. This is what
often happens when you have a nested Luke, when
you have to compare every single item in a list
to every other single item in that list. Can
you give me an example? Sure. Imagine you have
a list of 100 people in a room and you want to
see if any two of them share a birthday. The
simplest algorithm is to ask the first person
their birthday, then compare it to the other
99 people. Then you go to the second person and
compare their birthday to the other 98 people.
You see, for N people, you're doing roughly N
squared comparisons. So if you have 10 people,
it takes about 100 comparisons. If you have 100
people, it takes 10 ,000. If you have 1 ,000
people, it takes a million steps. The complexity
explodes. This is why a startup's new social
media app works perfectly fine with 50 beta testers
and then completely crashes the moment they get
5 ,000 users. Their algorithm was probably OM.
And it gets even worse than that, doesn't it?
It gets much, much worse. The truly terrifying
one is O2N, or exponential time. This is the
heat death of the universe algorithm. With exponential
time, if you add just one more element to the
input, you double the amount of work. Double
it. Double it. The traveling salesman problem
we mentioned earlier is a classic example. Finding
the absolute shortest route to visit own cities
requires checking a number of paths that grows
exponentially. If you can solve it for 20 cities,
adding the 21st city makes it twice as hard.
Adding the 22nd makes it four times as hard.
Very quickly, the problem becomes unsolvable
for even the fastest supercomputers. So our modern
security, like for banking and things, is basically
relying on the inefficiency of these kinds of
algorithms. Exactly. Modern encryption is built
on the fact that certain mathematical problems,
like factoring a very large number into its two
prime components, are believed to be in this
exponential or near exponential class for classical
computers. It's not that it's impossible. It's
that the O2n algorithm would take so long to
run that the sun will burn out before it finishes.
We rely on problems being intractable. We also
need to touch on space complexity. We always
focus on time, on speed, but computers have a
finite amount of memory. Right, and there's very
often a direct trade -off between the two. We
call it the space -time trade -off. You can frequently
make an algorithm run faster by allowing it to
use more memory. How does that work? Think of
it like this. You're a travel agent, and you
constantly need to know the driving distance
between any two major cities in the country.
Option A is to save space. Every time a client
asks, you use a mat and a formula to calculate
the distance on the fly. This takes time CPU
cycles, but uses very little memory. Option B
is to save time. You spend a week calculating
the distance between every possible pair of cities
and write it all down in a giant lookup table,
a huge book. Now, when a client asks, looking
up the answer is instant, very fast time complexity.
But you have to store and carry around this enormous
book, which takes up a huge amount of space or
memory. And modern computers have so much cheap
RAM that we usually lazy and choose option B.
We do. We are very wasteful of space today in
many applications because memory is cheap. But
back in the 1960s, programming for the Apollo
missions, or even today in small embedded systems
like the chip in your toaster, your car's engine,
space complexity is absolutely critical. You
have to be frugal. So we have the metrics for
judging them. Now I want to open what you called
the bestiary. I want to walk through the different
species of algorithms, the different paradigms,
because they really do have different personalities.
They really do. They have different philosophies
of problem solving. Okay, let's start with the
one we've touched on already, brute force. The
try -everything approach. Brute force is the
simplest, most obvious, and often dumbest way
to solve a problem. It's about systematically
trying every single possible option until you
find the right one. The quintessential example
is cracking a password. If you don't know the
password, you try A, then B, then C, then A,
A, A, A, C. It's guaranteed to work eventually.
Guaranteed. But for any non -trivial password,
eventually might be longer than the age of the
universe. It's the baseline against which smarter
algorithms are measured. OK, so a smarter approach
might be divide and conquer. Yes. Divide and
conquer is a very powerful and elegant strategy.
It's military strategy applied to math. You're
faced with a huge, scary problem. The philosophy
is don't try to solve the huge problem. break
it down into smaller, identical subproblems,
solve those little subproblems, and then combine
their solutions to solve the original big one.
This is the merge sort algorithm you mentioned
for sorting lists. Merge sort is the textbook
example. You have a huge unsorted list of numbers.
Don't try to sort it all at once. Just split
it in half. Now you have two smaller, easier
problems. Split those halves. Keep splitting
and splitting until all you have are tiny little
lists with just one number in them. And a list
with only one number is by d***. Definition already
sorted. It is. The conquer part was easy. Now
comes the combine part. You start merging those
little one -item lists back together into two
-item lists, but you merge them in sorted order.
Then you merge the two -item lists into sorted
four -item lists. You keep zippering them back
together, and at the end, you have one big, perfectly
sorted list. It's elegant, it's reliable, and
it's much, much faster. A dumb sort like bubble
sort. So dividing conquer is about breaking a
scary problem into a bunch of tiny, non -scary
problems. Precisely. Now, related to this is
the concept of recursion versus iteration. Two
different ways to implement that repeat a process
idea. Okay. Iteration is the one most people
are familiar with. It means using loops, a for
loop or a while loop. You're explicitly telling
the computer, do this thing 10 times or keep
doing this thing until this condition is met.
It's very direct. Recursion is a bit more mind
bending. A recursive algorithm is one that calls
itself to solve a smaller version of the same
problem. It calls itself. It calls itself. The
classic example is the Tower of Hanoi puzzle.
To move a stack of five disks, the recursive
solution is move the top four disks to the spare
peg, then move the bottom disk to the destination,
then move the four disks on top of it. But how
do you move four disks? Well, the algorithm calls
itself. To move four disks, you first move three
disks. It keeps breaking it down until it gets
to the simple case of moving just one disk. Sounds
elegant, but also potentially dangerous. Like
it could easily lead to an infinite loop. It
can if you're not careful. Every recursive algorithm
needs a base case, a condition that tells it
when to stop calling itself and just return an
answer. Without that, you get a stack overflow,
which is the recursive version of an infinite
loop. Let's move on to the greedy algorithms.
You call these the impulsive ones. The ones that
lack long -term vision. A greedy algorithm makes
the locally optimal choice at every single stage,
hoping that a series of locally optimal choices
will lead to a globally optimal solution. The
live in the moment algorithm. Exactly. Imagine
you are navigating a maze where every path is
lined with coins. A greedy algorithm stands at
a junction. It looks left and sees a path with
one coin. It looks right and sees a path with
five coins. It immediately goes right. It doesn't
care if the path on the right leads to a dead
end or a monster 10 steps later. the biggest
payoff right now. The marshmallow test of algorithms.
It always eats the marshmallow. Yes. It has no
impulse control. The traveling salesman problem
is another good example. The greedy approach
says, from where I am now, what is the absolute
closest city I haven't visited yet? Okay, I'll
go there. And it repeats that from every city.
And does that actually work? Does it give you
the shortest overall path? It gives you a path,
and it's very fast to calculate. But it usually
isn't the shortest path. It might send you to
a nearby city that is way out on a limb, forcing
you to make a very long trip later on. It gets
stuck in local optima. So if you need the absolute
best, perfect path, greedy fails, what do you
use instead? Well, for that kind of problem,
you might use dynamic programming. This is like
the smart, cautious older sibling of the greedy
algorithm. Dynamic programming also breaks a
problem down into subproblems, but it has a memory.
It uses a technique called memoization. Memoization.
That's M -E -M -O, not memorization. Right. Memoization.
It literally means writing it down in a memo.
Imagine you are calculating the Fibonacci sequence,
where each number is the sum of the previous
two. A naive recursive algorithm to find the
50th number would be incredibly slow because
it recalculates the same values over and over
and over again. Okay. A dynamic programming algorithm
says, wait a minute, I've already calculated
the value for the 10th Fibonacci number. I wrote
it down in my notebook. Instead of recalculating
it, I'll just look it up. It caches the results
of subproblems so it never has to do the same
work twice. And that's a huge speed up. It turns
many exponential problems into linear or polynomial
ones. This is fundamental to... how things like
Google Maps can find the shortest route so quickly.
It doesn't recalculate every road in the world
every time you ask for directions. It uses known
distances of smaller segments, solved subproblems,
to stitch together a full route. I want to touch
on one more category that seems really counterintuitive
to me. Randomized algorithms. Why on earth would
we want a computer, our machine of pure logic,
to do something random? This is for when the
problem is so monstrously big or complex that
finding an exact answer is just too expensive
or would take too long. Sometimes a probably
correct answer that you can get in a second is
much more valuable than a guaranteed correct
answer that takes a year. We generally have two
flavors. Monte Carlo and Las Vegas. Named after
the gambling meccas, I assume. They are, and
the analogy is perfect. A Las Vegas algorithm
is like a slot machine that is guaranteed to
eventually pay out the jackpot. It always gives
the correct, deterministic answer. But you don't
know how long it will take. You might get lucky
and it finishes in a second, or you might be
sitting there pulling the lever for an hour.
but you can trust the result when you get it.
Okay, so always correct, but runtime is random.
What about Monte Carlo? A Monte Carlo algorithm
is the opposite. It runs for a fixed, predictable
amount of time, but the answer it gives has a
small probability of being wrong. It's like playing
a round of poker. You finish the hand in a few
minutes, but you might have lost. It might say
the answer is 42, and I'm 99 .999 % sure about
that. Why would you ever accept a 99 % answer?
When is that good enough? A great real world
example is testing for prime numbers for cryptography.
We need to find huge prime numbers, numbers with
hundreds of digits, proving with 100 % mathematical
certainty that a number that big is prime is
very, very slow. But there's a Monte Carlo algorithm
called the Miller -Raben primality test. It runs
a few random checks on the number. If the number
passes all the checks, the algorithm says this
number is almost certainly prime. And almost
certainly is good enough for our online security.
It is. The probability of it being wrong after,
say, 100 rounds of testing is so astronomically
low -like, less than your chance of being hit
by a meteor, that for all practical purposes,
it's considered true. It's an engineering trade
-off. Engineering accepts tolerance. Pure math
does not. We've covered the mechanics, the types,
the theory. I want to move to the real -world
implications, specifically the legal side. If
these algorithms are such valuable tools like
industrial machines, can I own one? Can I get
a patent on an algorithm? This is a legal and
philosophical minefield. The short answer, in
the United States at least, is no, you cannot
patent math. You cannot patent the Pythagorean
theorem. You can't patent E. Masser. They are
considered fundamental truths of the universe,
abstract ideas, and they belong to everyone.
Software companies have thousands of patents.
Amazon has a pattern on one -click buying. That's
an algorithm. They do. And this is where the
legal nuance comes in. The distinction the courts
have tried to draw is between patenting the abstract
idea and patenting a specific practical application
of that idea. You can't patent the formula, but
you might be able to patent the machine or process
that uses the formula to do something tangible
in the real world. What's the key case there?
The landmark case is Diamond v. Dyer from 1981.
It was about a process for curing synthetic rubber.
Rubber curing. Not exactly the glamorous side
of Silicon Valley. No, but it was a critical
industrial process. The company had a computer
running a well -known mathematical formula, the
Arrhenius equation, to calculate the perfect
curing time. The algorithm constantly rated the
temperature inside the rubber mold and re -ran
the calculation to determine the precise moment
to open the press. The U .S. Patent Office rejected
their patent, saying, you're just patenting a
mathematical equation. But the Supreme Court
disagreed. They did. The Supreme Court overruled
them. They said that because this algorithm was
part of a larger process that was physically
transforming rubber from an uncured state to
a cured state, because it was interacting with
the real world in a tangible way. the overall
process was patentable. So if my algorithm just
sorts numbers on a computer screen, it's an abstract
idea and hard to patent. But if my algorithm
controls a robot arm that sorts physical apples
into bins, I can patent the whole process. That's
a good way of looking at it. Generally, yes.
But it is still a hugely debated area of law.
There's a lot of controversy. over software patents
stifling innovation if someone patents a fundamental
way of compressing video suddenly nobody else
can stream movies without paying them a license
fee it's a constant tension between protecting
inventors and allowing the free flow of ideas
needed for progress and speaking of progress
we have to look at the horizon because there's
a new kind of computer coming which means there's
a new kind of algorithm on its way We are entering
the era of quantum algorithms. You're a quantum
leap. It's a whole new paradigm. We hear the
buzzwords all the time. Quivets, superposition,
entanglement. Yeah. But from a purely algorithmic
standpoint, what actually changes? In a word.
Everything. All the classical algorithms we've
discussed, from Euclid to Google, are built on
the principles of a Turing machine. They operate
on bits. A bit can be a zero or it can be a one.
That's it. Quantum algorithms run on quantum
computers, which use qubits. And a qubit, because
of the principle of superposition, can be a zero,
a one, or. It can be in a state that is partly
zero and partly one at the same time. This allows
for a kind of massive parallelism that classical
computers can only dream of. So what does that
mean for problems? solving for our big O notation.
It means that for certain specific types of problems,
the complexity class can collapse. The most famous
example, the one that keeps cryptographers up
at night, is Shor's algorithm. And what does
that do? Remember, we said that factoring a huge
number into its prime components is an exponentially
hard problem for classical computers, that it
would take millions of years. That's the foundation
of most of our current encryption. Right. Shor's
algorithm, if you could run it on a large, stable
quantum computer, could factor those huge numbers
in hours, maybe minutes. It breaks RSA encryption
wide open. So it basically breaks the Internet
as we know it. It breaks a huge chunk of the
security infrastructure of the Internet. Yes,
it turns a classically intractable exponential
problem into a manageable polynomial one. That
is why organizations like NIST, the National
Institute of Standards and Technology, are in
a controlled panic. Well, they call it proactive
preparation. Just in 2024, they released the
first official standards for post -quantum cryptography.
So they're already building new encryption algorithms
that are designed to be hard even for quantum
computers to solve. It's the next phase of the
arms race, the code makers versus the code breakers.
It's a race that started with Al -Kindi and frequency
analysis in the ninth century. And it's continuing
today with quantum physicists and cryptographers.
It really is just one continuous line, isn't
it? Yeah. So let's try and wrap this all up.
We've gone on an incredible journey. We went
from Sumerian clay tablets to Al -Khorizmi's
name getting mangled to Ada Lovelace dreaming
of computer music to Alan Turing's theoretical
limits and now to quantum encryption. It's a
history of human problem solving, really. It
is. And we learned that algorithm isn't magic.
It's a rigorous recipe. We learned that efficiency
isn't about seconds. It's about scaling, about
avoiding those O -N or O -tine traps. We've met
the greedy algorithms, the divide and conquer
ones, the cautious dynamic programming ones.
It's a vast and fascinating ecosystem of thought.
But I want to leave our listeners with that provocative
thought you mentioned when we were prepping for
this. We spent this whole time talking about
deterministic algorithms. machines, logic, rigid
rules. But nature has its own algorithms, doesn't
it? Yes. And this is where the strict definition
starts to blur and get really interesting. If
you look at an ant colony foraging for food,
there's no central leader. No single ant knows
the map. But the colony as a whole runs a highly
efficient search algorithm. It uses pheromone
trails as a form of distributed memory to optimize
the path to a food source. It is a distributed
emergent biological algorithm. And what about
our own brains? Our brain is a massive neural
network. It doesn't run if -then code like a
laptop. It learns. It recognizes patterns. It
adjusts the weights and connections between its
neurons based on experience. It is a constantly
running adaptive learning algorithm. So in a
way, we are building these silicon -based algorithms
that are, in many cases, just trying to mimic
the biological algorithms that created them in
the first place. And we ourselves are the product
of four billion years of the grandest algorithm
of all. evolution by natural selection, a brute
force iterative process that optimizes for one
thing, survival and reproduction. So that leaves
us with the final question for everyone to chew
on. If a recipe is an algorithm and a bureaucracy
is an algorithm and an ant colony is an algorithm,
are you just running a very complex biological
algorithm right now? Are we the programmers or
are we just the code? That is a question that
might not have a halting state. You could loop
on that one for a good long while. I think I
will. This has been a fantastic deep dive. Thank
you so much. My pleasure. It was a lot of fun.
See you next time.