Imagine you were standing in the middle of a
massive, completely disorganized library. Like,
just books scattered absolutely everywhere on
the floor. Exactly. Yeah. Millions of books,
just everywhere. And you were looking for one
specific title. Now, you could be the fastest
runner on earth, right? Like a human sports car.
Yeah. But if your strategy is literally just
running down the aisles, looking at every single
spine one by one. You're gonna lose. You are.
A slow walker who just took a few minutes to
check a master index is going to beat you to
that book every single time. Because the physical
speed of the runner doesn't actually matter if
the fundamental method they're using to search
is flawed. You just can't outrun a bad strategy.
You really can't. And welcome to the Deep Dive.
I'm your host. And that disorganized library
is exactly the core of what we're unpacking today.
I'm really excited for this one. I've spent years
studying this exact topic, so it's going to be
fun to dig in. Awesome. So we are pulling from
a really comprehensive set of source material
today, centered around this deeply detailed Wikipedia
article on the analysis of algorithms. Right.
And the mission of this deep dive for you listening
is to basically figure out how computer scientists
actually measure if an algorithm, which is the
fundamental strategy your computer takes to solve
a problem, if that algorithm is actually efficient.
Because it's a lot more complicated than just
hitting a stopwatch. It is, and we're going to
see exactly why simply going out and buying a
faster computer is often the absolute worst way
to fix slow code. OK, let's unpack this. Efficiency
in computer science, like you said, isn't just
about stopwatches. No, not at all. It is usually
about finding a mathematical function, right?
Like a function that links the size of the input
you're giving the computer to the number of steps
it has to take or the amount of memory storage
it requires. Yeah, because an algorithm is really
just a recipe. OK, a recipe. Right. It's a specific
set of instructions. And what analysts really
need to know is what happens to those instructions
when the problem gets bigger. Oh, I see. Like
scaling up. Exactly. If we go from searching
a small bookshelf to searching the Library of
Congress, does the time it takes to follow that
recipe grow by just a little bit? Or does it
suddenly take, you know, an absolute eternity?
Right, and let's start with a really striking
visual from our source material that perfectly
captures this difference in growth. Imagine you
are looking for a specific name in a sorted list
of, let's say, 33 items. Just 33, pretty small.
Super small. Let's say you're looking for the
name Morin, Arthur, if you use what's called
a linear search. Which is the bad way. Right,
the bad way. Which basically means starting at
the top and checking every single name one by
one. Completely ignoring the fact that the list
is already in alphabetical order. Yeah, just
brute forcing it. Exactly. It takes 28 check
steps to finally find him in that list of 33.
And, well, 28 steps for 33 items doesn't sound
entirely catastrophic to a human. Like, you could
do that in a minute. Right. But in the computing
world, that's wildly inefficient. If you switch
your strategy and use a binary search algorithm
instead, it only takes five steps. Five steps
instead of 28? Just five. Wow. Just to visualize
how that works for you listening, binary search
actually takes advantage of the list being in
alphabetical order. It jumps right to the middle
of the list and asks, Is Morin before or after
this middle name? Exactly. And let's say it's
before. It immediately throws away the entire
back half of the list, then it goes to the middle
of the remaining games, asks the same question,
cuts the list in half again, and just repeats
that. Yeah, the underlying mechanism there is
having. Mathematically, theoretical analysis
shows that for a list of size n, a binary search
takes, at most, the base -2 logarithm of n steps.
OK, base -2 logarithm. Just so we are totally
clear here, that's basically just the mathematical
term for that having process, right? That's right.
Because you are repeatedly dividing the problem
in two, The number of steps grows logarithmically
rather than linearly. Got it. Whereas a linear
search can take up to n steps. So if the list
is a million items long, it might take a million
checks. Which is brutal. And this stark difference
in mechanisms brings us to this massive trap
that, according to the source, even experienced
programmers of massive tech companies still fall
into. Oh, consciously. Lying on empirical testing.
Yes. The empirical trap. So by empirical testing,
the force basically means just running the code
in the real world, like literally hitting go
on a stopwatch to see how fast the program finishes.
Right. And the problem with that is algorithms
are actually platform independent. OK. What does
that mean exactly? It means the pure logic of
a binary search can run on any machine. It can
be written in any programming language. Because
of that, real world benchmark tests, where you
just time the program, can be incredibly deceptive.
Because the hardware gets in the way. Exactly.
The hardware muddies the waters. The source provides
a brilliant example to prove this, actually.
Let's pit two computers against each other. OK,
I love this example. We have computer A, which
is this state of the art lightning fast machine,
top of the line processor, incredible specs.
But we are going to force it to run that slow
linear search algorithm. So it's the human sports
car checking every single book spine one by one.
Yes, perfect analogy. And then we have computer
B. Now, computer B is a much slower, older machine,
just a total clunker. But computer B gets to
run the highly efficient binary search algorithm.
So if we do a benchmark test on a tiny list,
say just 16 items, computer A finishes in 8 nanoseconds.
Computer B takes 100 ,000 nanoseconds. OK. So
if you're an engineer just looking at the results
of that empirical test, you'd say, wow, computer
A is absolutely crushing it. I mean, it's thousands
of times faster. by more of computer A. You would
jump to the conclusion that computer A is running
a far superior system, yeah, and you would be
dramatically wrong. Dramatically wrong. Because
computer A is exhibiting a linear growth rate,
its runtime is directly proportional to the input
size. If you double the length of the list, you
just double the time it takes. Right. Computer
B, however, exhibits that logarithmic growth
rate we talked about, because every single time
it takes a step, it wipes out half of the remaining
problem. Having it. Yeah, so if you exponentially
quadruple the input size, its runtime only increases
by a tiny constant amount. Okay, here's where
it gets really interesting. If we keep ramping
up the size of that list, that massive gap starts
to close, right? By the time we feed both computers
a list of 1 million items, they actually tie.
They do. They both take exactly 500 ,000 nanoseconds.
Yeah. That tie at 1 million items is the tipping
point. And the list obviously doesn't have to
stop at a million. Let's say we scale up the
input size to about 63 trillion items. OK, 63
trillion. That's 63 .772 times 10 to the 12th
power. Computer B, our slow clunker with the
smart algorithm, finishes searching that massive
list in just 1 .375 milliseconds. OK, wait. So
Computer B takes just over 1 millisecond. What
about computer A? The state -of -the -art machine
checking, one by one. Computer A will take exactly
one year to finish. A whole year. Seriously,
the math actually works out to a full year. It
works out perfectly to a year, because to check
63 trillion items linearly at the speed it was
going, the time just scales directly. That is
insane. Right. It proves, without a shadow of
a doubt, that algorithm design completely trumps
hardware speed when you are operating at scale.
A faster processor just cannot save you from
a linear growth rate. Okay, so if empirical Testing
is a trap, right? And if you can't trust a stopwatch
because hardware muddies the waters, how on earth
did computer scientists actually figure out a
way to prove one algorithm was better than another?
Well, they had to step away from physical testing
completely and use pure mathematics, specifically
what the source text calls asymptotic estimates.
Asymptotic estimates? Yeah, they allow us to
estimate the complexity of an algorithm for an
arbitrarily large input. Basically, we ask, what
happens to the math when the data approaches
infinity? Ah, okay. When things get infinitely
big. Exactly. To do this, computer scientists
use notations like big omega, big theta, and
the most famous one, big O notation. The term
analysis of algorithms and much of this methodology
was actually coined by the legendary computer
scientist Donald Newth. Right, Donald Newth.
Okay, so big O notation. You know, the way I
finally wrapped my head around this was thinking
about describing the absolute worst -case scenario
for a road trip. Oh, I like that. Yeah, like,
if you're going to visit a friend and you tell
them, look, at worst it will take me three hours
to drive there, you are placing an upper limit
on the time. Right, an upper bound. Exactly.
Even if there's traffic or a detour, it won't
take more than three hours. In mathematical terms,
Big O says that beyond a certain point, the runtime
of an algorithm will never be larger than a constant,
let's call it C, multiplied by a specific mathematical
function of the input size, f of n. Right. It
just places a hard ceiling on how bad things
can get as the data grows. That road trip analogy
perfectly captures the spirit of the upper bound.
For example, let's look at sorting data. If you
are sorting a list of numbers using an algorithm
called insertion sort, its worst case runtime
grows quadratically. Quadratically. Yeah. So
we say it is of order O of N squared. Let me
make sure I'm picturing insertion sort correctly.
That's kind of like organizing a hand of playing
cards, right? Yes, exactly. They can pick up
a new card and you have to compare it to every
single card already in your hand to find exactly
where it goes. That's the exact mechanism. If
you have N cards, you are doing roughly N comparisons
for every single one of those N cards. Hence,
N times N or N squared. Right. If you double
the amount of data, the time it takes quadruples.
If you triple the data, the time increases by
nine times. Which, as we saw with the linear
search versus binary search, is a growth rate
you really want to pay attention to. to because
an O of n squared algorithm is going to hit a
wall very fast. It will. It really will. Now,
while big O is incredibly useful for expressing
that worst case road trip scenario, our sources
make sure to note it can express average cases
too. Oh, interesting. So it's not just the worst
case. Right. Take another sorting algorithm.
Quick sort. Its absolute worst case scenario
is also O of n squared. But because of how it
divides data, On average, its runtime is actually
O of n log n. Which is better. Which is a much,
much flatter, faster curve. OK, so we have this
theoretical language to describe growth. We know
O of n squared is generally worse than O of n
log n at scale, because we are looking at the
shape of the mathematical curve. This raises
an important question, though. How can we mathematically
tally up the steps an algorithm takes to build
these curves if we haven't even defined what
a single step actually is in the math? Ah, right.
Good point. point, because if we are throwing
away the stopwatch and ignoring the computer's
actual hardware, what are we even counting? Exactly.
Like a step for a massive supercomputer is very
different from a step for a smart fridge. Completely
different. So for this theoretical analysis to
correspond usefully to actual runtime, we have
to guarantee that the time required to perform
a step is bounded by a constant. To standardize
this, computer scientists generally use two different
cost models. OK, cost models. The first is the
uniform cost model, sometimes called the unit
cost model. This model assigns a constant cost
of 1 to every single machine operation, regardless
of the size of the numbers involved. Wait, hold
on a second. Let me push back on that. Sure.
So under this uniform cost model, you're saying
adding 1 plus 1 takes the exact same amount of
time as adding two numbers that each have a billion
digits. Under that model, yes. But that seems
physically impossible. I mean, a computer actually
has to process all those extra digits. That feels
completely unrealistic for massive computations.
You've hit on the exact flaw of the uniform cost
model. It is physically impossible to process
a billion digits in the same time it takes to
process one. The physical logic gates in a computer
require more time to process more bits of information.
This assumption of constant time is a simplification.
And you're right, it's not always warranted.
which is exactly why the second model exists,
the logarithmic cost model. Okay, that sounds
like it counts for the size. It does. The logarithmic
cost model assigns a cost to every machine operation
that is proportional to the number of bits involved.
Oh, bits, so... Yeah, so adding those billion
-digit numbers would cost significantly more
theoretical steps than adding 1 plus 1. That
makes perfect sense. So if the logarithmic model
is more accurate to reality, why wouldn't they
just use it all the time? Well, because it is
incredibly cumbersome to calculate. Too much
math. Way too much math. In daily programming,
The numbers we deal with usually fit comfortably
within standard fixed memory sizes, like a 32
-bit integer or a 64 -bit integer. Because the
physical size of the numbers is capped by the
system, pretending they all take the same constant
time doesn't actually skew the mathematical results
enough to matter. So it's just practical. Yeah,
the uniform model is good enough for standard
software. The logarithmic model is really only
employed when absolutely necessary. So what's
a scenario where it's absolutely necessary? Like
when do you have to use it? The analysis of arbitrary
precision arithmetic. A prime example is cryptography.
Oh, like security stuff. Exactly. When you are
encrypting secure data like banking information
over the internet, you aren't working with normal
10 -digit numbers. You are working with astronomically
large numbers with hundreds or thousands of digits
just to make it impossible for hackers to guess
them. Wow. And the computer has to break those
massive numbers into smaller chunks just to add
or multiply them. In those cases, the size of
the number dramatically impacts the time it takes
to compute. So using the logarithmic cost model,
is essential to get an accurate O notation there.
Got it. So for everyday analysis, we just stick
to the uniform cost model, assuming each basic
step takes one unit of time. Right. So assuming
that uniform model, how do we analysts actually
peek under the hood and tally up the steps in
a piece of code? They evaluate the runtime complexity
by looking at the structure of the algorithm
itself. Usually, analysts will break down a piece
of pseudocode. Pseudocode. Yeah, which is like
a simplified, human -readable version of the
code. And they assign discrete time units to
the different instructions. They might say step
one takes time t1, step two takes t2, and so
on. OK, that seems simple enough. You just read
down the list and add up all the t's. It is simple
until the code loops. Especially nested loops
when you have a loop running inside another loop.
That's where the math gets tricky and where the
real runtime cost of an algorithm usually hides.
Okay, let me make sure I'm picturing this nested
loop math correctly. Is it kind of like a handshake
line at a party? Okay, let's hear it. Let's say
the party is our outer loop. The total number
of people at the party is n. Right. The first
person walks into the room. and there's only
one person to shake hands with. So one handshake.
That's the inner loop running once. Then the
second person walks in, and now there are two
people in the room, so they have to shake two
hands. The third person shakes three hands. And
this just keeps escalating until the last person,
person N, walks in and has to shake in hands.
That is a brilliant way to visualize it because
the inner loops iterations grow exactly like
that sequence, an arithmetic progression. It's
one plus two plus three. all the way up to n.
So if we want to know the total time that inner
loop takes, like the total number of handshakes
at the party, we have to add all those escalating
numbers together. And luckily, mathematics gives
us a shortcut formula for adding up an arithmetic
progression. The sum of that entire sequence
factors out to one half times the quantity of
n squared plus n. OK, so in formula terms, that's
one half times n squared plus n. Right. And when
we map out the entire algorithm, adding the constant
times for t1, t2, the test to see if the outer
loop should keep running and this newly factored
inner loop, we end up with a very long messy
polynomial equation. Sounds messy. But here is
the crucial takeaway for anyone evaluating complexity.
The highest order term dominates the growth rate.
The highest order term, meaning like the part
of the equation with the biggest exponent. Yes.
In our handshake equation, the highest order
term is the n squared. As n, the size of our
data, gets larger and larger, that n squared
part of the math grows so massively that it entirely
swallows all the smaller terms and the constant
factors. It just dwarfs them. Exactly. The linear
n terms, the 1 halves, the t ones, they all become
statistically insignificant. Because if n is
a million, a million squared is a trillion. Yep.
and adding a few extra million on top of a trillion
from the other parts of the equation doesn't
really change the trajectory of the curve. Not
at all. We can mathematically prove that the
function's growth is bounded by that n squared.
Therefore, the algorithm's runtime order is officially
declared to be O of n squared. We've proven it,
theoretically, mapping the code directly to a
curve without ever needing a physical stopwatch.
So what does this all mean? We've built this
entire theoretical framework on the assumption
that data approaches infinity. That's why big
O works. Because at infinity, n squared gets
so unimaginably huge, it just swallows everything
else. Yes, that's the theory. But we don't live
in an infinite world. We certainly do not. And
that introduces a massive real -world plot twist
in the analysis of algorithms. Plot twist. Yeah.
Big O focuses on asymptotic performance, what
happens as things get unimaginably large. But
real -world data is practically always limited
in size. because it's limited by the physical
constraints of addressable memory, right? Yeah.
Our computers only have so much RAM to hold data
in the first place. Precisely. On a 32 -bit machine,
your limit is usually 4 gigabytes, which is the
strict technical term for how computers measure
a gigabyte based on powers of 2. Right. On a
modern 64 -bit machine, the addressable limit
is 16 XB bytes. Now, 16 XB bytes is a staggering
amount of memory, but it is deeply physically
finite. Right. It's not infinity. And because
our data cannot actually reach infinity, an incredible
thing happens to the math. The constant factors
suddenly matter a whole lot. The constant factors.
The exact things we just ignored and threw away
when we were factoring our nested loop. We threw
away the constant overhead because n squared
was assumed to get infinitely big. But if n is
kept relatively small by physical memory limits
or just the practical size of a user's data,
the overhead of a theoretically fast algorithm
might actually make it run slower than a theoretically
slow algorithm. That is wild. And I love the
example our sources provide for this. It's about
an algorithm called TimSort. Oh, TimSort is f
- Fascinating. Yeah. Now we talked about insertion
sort earlier with the playing cards. We proved
it was O of n squared. It grows quadratically.
It's generally considered a bad, slow algorithm
for large data. Correct. And then there are highly
efficient algorithms, like merge sort, which
operated that much flatter O of n log n curve.
Under big O notation, merge sort wins every single
time as the data scales up. But TimSort is what's
known as a hybrid algorithm. It's actually the
default sorting algorithm used in incredibly
popular programming languages like Python. Which
is everywhere. Right. TimSort uses the highly
efficient merge sort for the big chunks of data.
But when the data chunks get small enough, TimSort
actually deliberately switches back to the theoretically
inefficient insertion sort. It actively chooses
to use the O of N squared algorithm. Yes. And
why would it do that? Because the highly efficient
merge sort works by constantly dividing lists
and allocating new memory spaces to merge them
back together. That takes a lot of time behind
the scenes. Right. That requires a lot of complex
overhead. Insertion sort is incredibly simple.
It just swaps the playing cards in place. For
small amounts of data, the simple theoretically
terrible algorithm just runs faster in reality
because it skips all the heavy setup time. It's
a perfect compromise between pure mathematical
theory and practical engineering. For small datasets,
an asymptotically inefficient algorithm with
low overhead is absolutely more efficient in
practice. What a journey! I mean, we started
off proving how deceptive empirical speed tests
can be with our state -of -the -art computer
losing to the clunker because of a linear versus
logarithmic search. That showed us why we needed
the theoretical landscape of big O notation and
cost models to truly understand growth curves.
And we learned how analysts mathematically evaluate
code by counting discrete steps and looking for
the dominant highest order term that swallows
the rest. But then we brought it all back down
to earth, realizing that in a finite world with
memory limits, practical compromises like TimSort
are totally necessary. The constant factors still
have a voice. The stakes for getting this right
are incredibly high, too. The source material
emphasizes this explicitly. The accidental or
unintentional use of an inefficient algorithm
can dramatically impact system performance. Absolutely.
In time -sensitive applications, an algorithm
taking too long can render its results entirely
useless. If a weather prediction algorithm takes
48 hours to predict tomorrow's weather... You've
missed the window. You missed it. The data is
worthless. Or, you know, it devours an uneconomical
amount of computing power. which brings up one
final really provocative thought from our sources.
We've spent almost this entire deep dive talking
about efficiency in terms of time, runtime. Right,
how fast it goes. But this mathematical methodology
applies equally to other resources though. Exactly,
it applies to space. Memory consumption. The
text gives a chilling example of a file management
algorithm that attempts to reallocate memory
based on file size. If designed poorly, The memory
consumption exhibits an exponential growth rate
order O of 2 to the N. Oh man, O of 2 to the
N is a terrifying curve. It is a hyper rapid,
utterly unmanageable growth rate. Think about
how a badly defined algorithm like that might
actually work. Imagine a program scanning your
hard drive. It finds a shortcut folder that accidentally
points back to its own parent folder. The algorithm
copies the parent folder into memory, then follows
the shortcut and copies the parent folder again
inside itself. Right, it creates a recursive
loop. doubling the amount of memory it's holding
every single cycle. Two megabytes, four, eight,
16, 32. Within moments, it would exponentially
duplicate data until it consumes all available
memory and completely crashes the system. The
space complexity becomes a fatal bottleneck long
before time complexity even factors in. And this
leaves you with something really fascinating
to ponder. For decades, we've relied on hardware
engineers to bail us out of bad memory -hungry
code, but building faster processors and bigger
hard drives. The whole idea behind Moore's Law.
We just kept doubling the transistors on the
chips. Right. But physical computing hardware
is currently hitting atomic limits. You can only
make a transistor so small before quantum mechanics
ruins the signal. It's just physics. Yeah. We
literally cannot just build faster machines the
way we used to. Which means the ultimate bottleneck
of the future is shifting away from the silicon
microchip. It is shifting entirely onto the human
mind's ability to design the perfect space and
time efficient algorithm. If you want to win
the race, you can't rely on upgrading the engine
anymore. You have to know how to avoid the human
sports car trap and build a better index for
the library.