Why Code Breaks at Scale
When data grows from 100 to 100,000 records, an algorithm that compares every pair jumps from 10,000 comparisons to 10 billion, minutes of work for code that used to run in a blink. Two questions fix this:
- How does it grow? What happens to time and memory as data gets bigger?
- Where does it live? Is data shared in memory or truly separate?
For a deeper dive on the foundational concepts of how computers store everything in binary and how algorithms scale, check out How Computers Work: From Binary Numbers to CPU Design Explained and Understanding Time and Space Complexity: A Comprehensive Guide to Big O Notation.
How Machines Store Data
Binary Counting
- Computers use base 2 (binary) with two digits: 0 and 1
- A bit is one switch; 8 bits = 1 byte
- Each bit position doubles the previous value (1, 2, 4, 8, ...)
Example: Convert 89 to binary
128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 ----|----|----|----|---|---|---|--- 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1
89 = 64 + 16 + 8 + 1 = 01011001
For a practical guide on converting between number systems in Python, see Understanding Number Systems and Binary Conversion in Python.
Signed Numbers & Overflow
- Unsigned: 0 to 255 for 8 bits
- 2's complement: leftmost bit = -128 (range -128 to +127)
- Overflow: 127 + 1 wraps to -128
Hex Shortcut
- Base 16 fits 4 bits per digit: 0-9, A-F
0x53=01010011= 83 unsigned, or 'S' in ASCII
Decimal Fractions Are Often Approximations
- Binary can't store 0.1 exactly, just like decimal can't store 1/3 exactly
0.1 + 0.2 ≈ 0.30000000000000004- Watch for: money, equality checks, loops
Memory Hierarchy
- RAM (volatile): fast, erased on power loss, the whiteboard
- Disk (non-volatile): slow, survives restarts, the notebook
How Code Grows: Big O
Big O describes worst-case growth in operations or memory as input size grows:
- O(1): Constant, array lookup by index
- O(n): Linear, simple search through unsorted list
- O(n²): Quadratic, nested loops (like the duplicate check earlier)
- O(log n): Logarithmic, binary search
If you need a refresher on the basics of Big O and how to apply it to your code, refer to Time & Space Complexity Basics: Big O Notation Explained for DSA.
Key Data Structures & Their Costs
Arrays
- Fast read/write by index: O(1)
- Slow insert/delete in middle: O(n)
Hashmaps (Dictionaries)
- Average lookup: O(1)
- No order guarantee; collisions can degrade
Trees (BST, Balanced)
- Search, insert, delete: O(log n)
- Good for ordered data
Graphs
- Connections between items; algorithms vary
- Common questions: shortest path, reachability
For a complete overview of the most important data structures and their performance characteristics, see Comprehensive Guide to Core Data Structures and Algorithms.
Common Bugs & Fixes
1. Shared References
- Copying an object only copies the reference, not nested objects
- Fix: Deep clone when needed
2. Text Encoding Mismatches
- UTF-8 stores English in 1 byte; accented characters take 2-4 bytes
- Opening UTF-8 text as ISO-8859-1 produces garbled characters
- Fix: Know your encoding at every boundary
3. Overflow
- Choose 64-bit integers for counters, file sizes, money
- Know what your language does on overflow (wrap, error, grow)
Putting It All Together
The course applies every concept to a real-world case: debugging a slow API endpoint. You trace through memory layout, algorithm choice, and threading issues to understand why the code slows and how to fix it.
Have you ever written code that worked fine on a hundred records and then got very slow once real data arrived? Or sat
in an interview, heard the words big O, and known the term, but not what it meant for your code? If that sounds
familiar, it's a very common gap. Most coding courses teach you how to write code. Very few show you what that code
costs once the data gets big. This course is for people who already write code, but never had the computer science
behind it explained. Some people learned from tutorials or on the job. Others went through a boot camp or now build
mostly with AI tools. Those are all good ways to start. They just tend to skip one thing. That's why code works the way
it does and why it sometimes doesn't. Here's a small example. Say your app checks a customer list for duplicates.
It takes each customer and compares them with every customer in the list. With 100 customers, that's 100 * 100. That's
about 10,000 comparisons and it's over in a blink. Now the list grows to 100,000 customers. That's 100,000 *
100,000. That comes to 10 billion comparisons. The code didn't change at all. Only the data did. And the same
check can now take minutes. Here's another one. Say you copy a customer record so you can try out a discount on
the copy. You lower the prices in the copy's order list. Then you look at the original customer and those prices have
dropped too. Nothing in the code looks wrong. You made a copy and you change the copy, but only the record was
copied. The order list inside it wasn't. Both records still point at the same list in memory. So a change through one
shows up in the other. Those two bugs lead to the two questions this course keeps coming back to. The first is how
does it grow? That's the duplicate check. What happens to your code's time and memory when the data gets much
bigger? The second is where does it live? That's the shared order list. Where does your data sit while the
program runs? And is it yours alone or shared with something else? Once you start asking those two questions, slow
code and strange bugs stop being a guessing game. The course starts with the machine itself. You'll turn a number
into zeros and ones by drawing a row of boxes and filling them in. You'll see why a counter can suddenly go negative
and why 0.1 + 0.2 isn't quite 0.3. You'll also see why some memory forgets everything the moment the power goes
off. Then the course looks at how work grows as your data grows. You'll learn big O by reading real loops, not by
memorizing a chart. After that come the data structures you use every day like arrays, hashmaps, trees, and graphs. For
each one, the question is simple. What does it cost and when should you pick it? The last part looks at what happens
while your code runs. That covers garbage collection, threads, race conditions, and async code. Then it all
comes together in one realworld case. A slow API endpoint. One address in a web service that your app calls gets
investigated from start to finish. You don't need a particular language and you don't need advanced math. If you've
written some code, you're ready. Every lecture is built around a real example with diagrams on screen. Now and then a
lecture asks you to work something out first. Pause the video and try it before you hear the answer. The lectures are
short and each one builds on the ones before, so take them in order if you can. Each module also has a quiz, notes,
and interview questions to check yourself with. This matters even more now that AI can write code in seconds.
Someone still has to judge whether that code is right and whether it will hold up. that someone is you. And once these
ideas are clear in your head, they're much easier to explain to someone else, like a newer teammate or an interviewer.
So that's the course. It starts with how the machine stores your data. And it ends with a real debugging case. If you
want to understand what's going on underneath your code, let's get started. When you write code, you work with
names. You might have a variable called total or a list called customers, but the computer never sees those names. All
it has is bits, tiny switches that are either off or on, stored at numbered places in memory. Say total holds the
number 42 inside the machine. That's eight switches with three of them on. The same eight switches could also mean
a letter or part of a color. It all depends on how your code reads them. This module starts right there. It shows
how whole numbers, negative numbers, text, and fractions all become bits. Then it looks at where those bits sit
while your program runs from fast memory beside the processor all the way out to the disk. It finishes with what happens
when you pass your data around. That's the where does it live question and it comes up again and again in this course.
So let's start with how a computer counts. Think about how you count. You have 10 digits from 0 to 9. When you
reach 9 and run out of digits, you start a new column and 9 becomes 10. Every number you write is built that way.
That's why it's called base 10. The base is simply how many digits you have to work with. A computer has only two
digits, 0 and 1. So, it counts in base 2. That's also called binary. Why only two? Inside the hardware, every piece of
data is held in something that has two states. In a memory chip, it might be a tiny charge that's either there or not
there. On a wire, it might be a voltage that's high or low. Two states are easy to tell apart, even in tiny parts. So,
the computer reads each one as a zero or a one. One of those zeros or ones is called a bit. A bit is the smallest
piece of information a computer can store. Think of it as a light switch. It's either off or on, and it can't be
both at once. On its own, one bit can only answer a yes or no question. The power comes from putting bits together
in groups. Watch what happens as you add switches. One switch gives you two patterns, off or on. Two switches give
you four patterns. Both can be off or both can be on or just the first is on or just the second. Now try three
switches. How many patterns can you make? Take a second and count them before I answer. The answer is eight.
Every time you add a switch, the number of patterns doubles. That's because the new switch can be off or on for every
pattern you already had. Keep doubling and four switches give 16 patterns. Eight switches give 256.
That's 2 multiplied by itself 8 times. It's written as 2 to the power of 8. A group of eight bits has its own name.
It's called a bite. Memory, file sizes, and storage are all measured in bytes. So, how can a bite stand for a number?
It uses the same trick you already use in base 10. Take the number 235. The two means 20 hundreds. The three
means three 10 and the five means five 1's. Each digits value depends on where it sits. Each position is worth 10 times
the one to its right. Binary uses the same idea but with twos. Each position is worth twice the one to its right. So
on the far right, a position is worth one. The next is worth 2, then 4, then 8. The values keep doubling and the
position on the far left of a bite is worth 128. Now you can read a binary number. Just add up the positions that
hold a one. Take one 01. The one on the right is worth one. The middle position is worth two, but it holds a zero, so it
adds nothing. The one on the left is worth four. 4 + 1 is 5. So 1 0 1 in binary is the number five. In a full
bite, 5 gets five extra zeros in front. Those zeros add nothing. So the value is still five. Here's what to take away. A
computer counts in base 2 with bits that are either off or on. Eight bits make a bite. And a binary number is just the
total of the positions that are switched on. A computer stores every number as zeros and ones. So how do you turn a
number like 89 into binary? You only need one method, and you can do it with a pencil and paper. Picture eight empty
boxes in a row. That's one bite. Each box will hold a zero or a one. Now give each box a label. Above the box on the
far right, write one. Then move left and double the label each time. The labels grow from 1 to 2, then 4, then 8. Keep
going, and the box on the far left is worth 128. These labels are the place values of binary. Here's a number to
convert. Say an online store sold 89 copies of a book today. You want to see that count as a bite. Start with the box
on the far left. Does 128 fit into 89? No, it's too big. So, that box gets a zero. Move to 64. Does it fit into 89?
Yes. Put a one in that box and subtract. 89 - 64 leaves 25. Next comes 32. It doesn't fit into 25, so that box gets a
zero. 16 does fit. Put a one there. 25 - 16 leaves 9. 8 fits into 9. Put a one in that box and you have one left.
Four doesn't fit into one, so that box gets a zero. Two doesn't fit either, so that's another zero. The last box is
worth one, and that's exactly what's left. Put a one there. Nothing remains, so you're done. Now read the boxes from
left to right. You get 0 1 0 1 1 0 0 1. That's 89 in binary. Always check your answer. Add up the labels of the boxes
that hold a 1. 64 + 16 is 80. Add 8 and you get 88. Add one more and you're back at 89. The answer checks out. So the
whole method has two steps. Work from left to right. If the label fits into what's left, write a one and subtract
it. If the label doesn't fit, write a zero and move on. Now try one yourself. Pause the video and convert 150 into 8
bits. Here's how it goes. 128 fits and 22 is left. 64 doesn't fit and neither does 32. 16 fits and six is left. 8
doesn't fit. Four fits and two is left. Two fits and nothing is left. The last box gets a zero. So 150 is 1 0 0 0 1 0 1
1 0. The same boxes also show you the limits of a bite. Switch every box off and the value is zero. That's the
smallest number you can write. Now switch every box on and add all eight labels together. You get 255.
That's the largest. There's a quicker way to find that top value. 8 bits give 256 patterns. Counting starts at zero.
So the top value is one less. That's 255. So what happens if the store sells 300
copies? 300 doesn't fit in eight boxes. Even with every box switched on, you only reach 255.
You'd need a 9th box worth 256. That's why bigger numbers get 2 4 or 8 bytes. There's one catch. That range
only holds when every pattern means zero or a positive number. That's called an unsigned number. Draw a bite as eight
boxes and switch them all off. That's zero. Switch them all on and you get 255.
Every number in between is zero or positive. A number like that is called unsigned because it never needs a plus
or minus sign. But plenty of numbers do need a sign. A bank balance can drop below zero. So can a temperature. So can
a store's stock count when more items get returned than sold. How do you store a minus sign when all you have is zeros
and ones? Let's try the most obvious idea first. Take the box on the far left and give it a new job. Instead of being
worth 128, it now answers one question. Is this number negative? A zero means no and a one means yes. That box is called
the sign bit. The other seven boxes still hold the size of the number. Their labels run from 1 up to 64. Switch all
seven on and they add up to 127. With the sign bit off, that's plus 127. Turn the sign bit on and it's minus 127. That
seems to work, but there's a problem hiding in it. Switch all seven number boxes off. With the sign bit off, you
get zero. Now turn the sign bit on. You get minus 0. But 0 is just zero. Having two patterns for it wastes one and it
makes adding numbers more complicated. This first idea is called sign and magnitude. It's easy to picture but
computers don't use it for whole numbers. What they use instead is called 2's complement. The change is small. The
box on the far left keeps its value of 128, but now it counts as negative. It's worth minus 128. Every other box keeps
its normal value. Now you read the bite exactly as before. Add up the boxes that are switched on. Try 0 1 0 0 0
1. The left box is off. Only 64 and 1 are on. That's 65, a positive number. Now try 1 0 0 0.
Only the left box is on. So the value is minus 128. Here's one to try yourself. What number is 8 1's in a row? Pause and
add it up. Start with - 128. The other seven boxes add up to 127. - 128 + 127 is -1. So a bite full of ones means
minus1. And minus0 is gone. There's only one way to write zero now with every box off. that frees up a pattern. So the
range runs from minus 128 up to plus 127. And the same adding circuit works for signed and unsigned numbers, which
makes adding and subtracting much simpler to build. That's why nearly every computer today stores signed whole
numbers this way. Notice what hasn't changed. Both kinds use the same 8 bits and the same 256 patterns. Unsigned
spends all of them on zero and above. signed spends half of them on negative numbers. The bits themselves don't know
which kind they are. The type in your code decides how to read them. So, a separate sign bit is the obvious design,
but it gives you two zeros. Two's complement makes the left box count against you instead. And that one change
fixes it. Every whole number in your code is stored in a fixed number of bits. That means every number type has a
ceiling. Here's how to find it and what happens when a value goes past it. Start with one bite that holds zero and
positive numbers only. With every box switched on, it reaches 255. That's the ceiling for eight bits. Say a
store counts each customer's loyalty stamps in a bite like that. Every purchase adds one stamp. After 255
purchases, every box is already on. There's nowhere left to go. So add eight more boxes. Now you have 16 bits or two
bytes. The labels keep doubling as you go left. Switch all 16 boxes on and you can count up to 65,535.
Eight extra boxes took the ceiling from 2555 to over 65,000. And it keeps growing. 32 bits reach
about 4 billion. When half of those patterns go to negative numbers, that's about 2 billion each way. 64 bits go far
beyond that. But every size still has a ceiling. Here's what hitting a ceiling looks like in real code. A website
counts its page views in a 32-bit signed number. For months, the count climbs normally. Then one morning, the
dashboard shows a large negative number. To see why, shrink the problem down to one signed bite. In the usual signed
format called 2's complement, the box on the far left is worth minus 128. So the biggest value is a zero followed by
seven 1's. That's plus 127. Now add one. It works like carrying in normal addition. All the ones roll over to zero
and the carry lands in the box on the far left. You're left with a 1 followed by seven zeros and that box is worth
minus 128. So 127 + 1 has turned into minus 128. Going past the ceiling is called overflow. When the value jumps to
the other end like this, it's called wrapping around. The page view counter did exactly the same thing just with 32
bits. It went past about 2 billion and wrapped around to about minus 2 billion. Whether your code wraps depends on the
language. Java wraps and it gives you no warning. Swift stops the program with an error instead. Python's whole numbers
just keep growing. Other languages make other choices. So when a counter does something strange, find out what your
language does. The fix starts with choosing the type. Ask how big this value could ever get, not how big it is
today. For counters, file sizes, and money and cents, that often means 64 bits. And when a value could still pass
its ceiling, decide what should happen. You might reject the update, raise an error, or move to a bigger type. So more
bits raise the ceiling, but they never remove it. A debugger is a tool that pauses your program so you can look
inside it at its variables and its memory. When you look at raw memory that way, you rarely see long rows of zeros
and ones. You see things like 0x53. But the computer stores everything in binary. So why do developers write it
some other way? The answer is a number system called hexadimal or hex for short. It's a shorter way to write the
same bits. To see how it works, follow one bite 0x53 all the way through. Hex is base 16, so
it has 16 digits. The first 10 are the usual 0 to 9. After that, it borrows letters. A stands for 10 and B stands
for 11. The letters go on up to F and F stands for 15. Why 16? Because it fits binary perfectly. Draw four boxes with
the labels 8, 4, 2, and 1. Switch them all off and you get zero. Switch them all on and you get 15. So four bits give
exactly 16 patterns and one hex digit has exactly 16 values. Every group of four bits becomes one hex digit. And
since a bite is 8 bits, every bite is exactly two hex digits. Now take the bite in binary. It's 0 1 0 1 0 0 1 1.
Split it down the middle. The left half is 0 1 0 1. Using the labels, that's 4 + 1. So the left half is 5. The right half
is 0 0 1 1. That's 2 + 1. So it's 3. Put them together and the bite is 53 in hex. Programmers write it as 0x53.
The 0x at the front just says the number is written in hex. That's why debuggers use hex. Eight zeros and ones become two
short characters and you can still read every bit inside them. Now try one yourself. What is 0x FF in binary? Pause
and work it out. Each F is 15 and 15 means all four boxes are on. So FF is eight ones in a row. That's a whole bite
with every box switched on. Hex has one limit though. It tells you which bits are there. It doesn't tell you what they
mean. Go back to 0x53. Read it as an unsigned number and it's 83. Read it as text and it's the capital
letter S. That's because the standard code for English letters called ASI gives S the number 83. UTF8 uses the
same number. The bite doesn't contain a tiny letter S. It's eight switches and the program decides how to read them. 0x
FFF works the same way. Read it as an unsigned bite and it's 255. Read it as a signed bite where the left
box counts as minus 128 and it's minus1. The switches are the same, but the answers are different. Once you see
that, you'll spot hex in lots of places, always for the same reason. It's a short way to show bytes. A web color is a good
example. It's three bytes in a row, one each for red, green, and blue. The color FF 000000
has red turned all the way up and the other two off. That's pure red. So hex is binary written short with four bits
to every digit. What those bits mean is up to the type that reads them. A computer can only store numbers. So how
does it store a name, an email, or a message? It turns every letter into a number. And that only works if everyone
agrees which number means which letter. Here's what happens when they don't agree. A customer named Jose signs up
and your app shows his name just fine. Then someone exports the customer list to a spreadsheet. There, his name comes
out as J O S followed by two odd symbols instead of the A. The bytes for his name are all still in the file. Two programs
read the same bytes and disagreed about what letters they meant. Let's build the agreement from the start. Picture a
table with two columns. On the left is a number and on the right is a letter. 65 means capital A. 66 means capital B.
Every letter, digit, and punctuation mark gets its own row. A table like that is called an encoding. The oldest one
still in use is called ASKI. It covers English letters, digits, and punctuation. Every row fits in a single
bite. For English text on early computers, that was enough. It wasn't enough for the rest of the world.
Accented letters needed numbers, too. So did other alphabets, Chinese characters, and later emoji. A single bite has only
256 patterns, and that's nowhere near enough rows. So people built a much bigger table called Unicode. It gives a
number to each character and symbol used in text across nearly every writing system. It has room for over a million
of them. Each number in that table is called a code point. Unicode decides which number each character gets, but it
doesn't decide how to store that number as bytes. That's a separate step, and the most common way to do it today is
called UTF8. UTF8 has one clever rule. The old English characters still take one bite
each, so old files keep working. Other characters take two, three, or four bytes. So, how many bytes does Jose
take? Count them before I answer. It's five. J, O, and S take one bite each. The A takes two. So, in UTF8, the length
of a string in bytes and its length in characters are different things. Most emoji take four bytes each. So, 10 of
them come to about 40 bytes. Some emoji take even more. Some languages also count string length in their own way. So
a single emoji can show a length of two. Now the classic bugs make sense. Say a program assumes one bite per character.
It meets a three byte character and it shows three garbage symbols or a question mark. Or a UTF8 file gets
opened with an older western encoding. Each accented letter turns into a pair of odd symbols. That's Jose in the
spreadsheet. Or a string gets cut in the middle of a character and you get a broken symbol at the end. Every one of
these is the same mistake. Some code read bytes as characters without knowing the encoding. Know the encoding of your
text when it enters your program and know it when it leaves. Today, UTF8 is widely used and a safe choice. And be
suspicious of any code that measures or cuts text bytes when it means characters. It can break the moment a
character from outside plain English shows up, even a curly quote. When text looks broken, ask two questions. Which
encoding wrote these bytes? And which encoding is reading them? In bugs like these, the cause is usually a mismatch
between the two. Try this in many programming languages. Add 0.1 and 0.2. Then check whether the answer equals
0.3. You might get 0.3, then a long row of zeros, then a four at the very end. That extra digit looks strange, but it
isn't a bug. It comes from how computers store fractions. Start with something familiar. Divide 1 by 3. You get 0.333.
And the threes never stop. Our decimal system can't write 1/3 exactly. Computers face the same problem, but
with different fractions. Binary fractions use halves, quarters, 8s, and smaller pieces. Each piece is half the
size of the one before. Some fractions fit perfectly. For example, 3/4 is 1/2 + 1/4. But 1/10th is different. Try
building 1/10th out of halves, quarters, 8, and smaller pieces. You can get closer and closer to 1/10th. But no
matter which pieces you combine, a fixed number of them can never make exactly 1/10th. The binary digits keep going
without ending. So 1/10enth never ends in binary just as 1/3 never ends in decimal. But computers can't store an
endless string of digits. They keep a limited number and store the nearest value they can. That value is slightly
different from the number you meant. When you add two of those values, the tiny differences can show up in the
result. That's why adding 0.1 and 0.2 usually doesn't give exactly 0.3. Numbers stored this way are called
floatingoint numbers or floats. A common 64-bit float keeps about 15 to 17 digits of accuracy. That's enough for many jobs
like graphics and measurements. But three situations need extra care. The first is money. Imagine adding up prices
across thousands of orders. Across many calculations, those tiny errors can change the final amount. For money that
has to be exact, store whole numbers of cents or use a decimal type, a number type built to store decimal values like
0.1 exactly. The second is comparing numbers. Two calculations that should give the same result might differ very
slightly. So instead of checking whether they're exactly equal, check whether they're close enough. That small allowed
difference is called a tolerance. The third is loops. Imagine adding 0.1 again and again until the total equals exactly
1.0. Because of the tiny errors, the total might never be exactly 1.0. So the loop could keep running forever. A safer
way is to count from 1 to 10 and work out the decimal from the count. So remember the main idea. Binary can store
some fractions exactly, but many decimal fractions need endless binary digits. Floats store a close guess, not always
the exact value. And whenever a calculation must be exact, choose a number type that's built for that job.
Every value your program uses has to sit somewhere while the program runs. And a computer has more than one place to put
it. To keep things simple, start with the two big ones. There's memory that forgets and memory that keeps. Think of
a whiteboard and a notebook. A whiteboard is quick to write on and quick to read, but at the end of the
day, it gets wiped clean. A notebook is slower to write in, but what you write there is still there tomorrow. The
computer's whiteboard is RAM. That stands for random access memory. It's where a running program keeps its data.
It's fast, and every bite in it can be reached directly by its address. But RAM needs power to hold on to its bits.
switch the machine off and everything in RAM is gone. And if your program crashes or restarts, whatever it was holding in
RAM is gone, too. That's why RAM is called volatile memory. Volatile just means it doesn't last. The computer's
notebook is the disc. Today, that's usually a solid state drive, an SSD. Older machines use a spinning hard
drive. Either way, the disc keeps its data with the power off. That's why it's called nonvolatile or persistent
storage. It's where your files live and where a database keeps its tables. So why not keep everything on the disc?
Because the disc is far slower. Even a fast modern drive can be hundreds to thousands of times slower than RAM. And
why not keep everything in RAM? Because RAM is more expensive per bite and it forgets. So computers use both. RAM is
for the work happening right now. The disk is for anything that has to survive. Here's what that means for a
running program. When you open a file, the program copies it from the disk into RAM. All the editing then happens in RAM
where it's fast. When you press save, the program writes the bytes back to the disk. If the power fails before you
save, your changes are gone. They only ever lived on the whiteboard. The same rule shows up in an online store. Say
the store keeps every shopping cart only in the memory of its server. Then the server restarts and every cart is
suddenly empty. But the orders were written to a database on disk so they survive. So before you store something,
ask a simple question. Does this need to survive a restart? If it does, it has to reach persistent storage. But how does
the processor get data out of RAM fast enough? The answer is that RAM isn't the closest memory to the processor. The
CPU, the processor, holds the values it's working on right now in a handful of tiny slots called registers. Reading
a register is about as fast as anything gets. Just next to the CPU is a small, very fast memory called the cache. It
keeps copies of data from RAM that the processor will probably need again soon. So, picture the whole thing as layers.
Registers are closest to the processor, then the cache, then RAM. Below RAM is the disk, and further still is anything
across a network. As you move away from the processor, each layer gets bigger and cheaper per bite. Each one also gets
slower. A trip to RAM can take about 100 times longer than reading the fastest cache. Treat those numbers as rough
because they change from machine to machine, but the order holds almost everywhere. So, there are two questions
to ask about any piece of data. How close is it to the processor? And will it still be there if the power goes off?
Most code treats memory as one big space where every read costs the same. The hardware doesn't work that way, and
sometimes it shows. Say you have a big grid of numbers, like a spreadsheet with a,000 rows and a,000 columns. You write
two loops that add up every number in it. The first loop walks the grid row by row. The second walks it column by
column. Both loops do exactly the same amount of adding. But on a large grid, the second one is often several times
slower. The exact gap depends on the language, the hardware, and the size of the grid. Before I explain, make a bet.
Why would the order of reading matter at all? The answer is a small, very fast memory that sits right next to the
processor. It's called the cache. To see how it works, start with how far away the data is. The processor or CPU does
the actual work, like adding and comparing. Your program's data lives in RAM, the main memory. RAM is fast by
everyday standards, but next to the processor, it's a long wait. The fastest cache can answer in a fraction of the
time RAM takes. If the CPU had to go to RAM for every single number, it would spend most of its time waiting. So, the
cache keeps copies of data the processor is likely to need soon. There are usually a few levels of it. Each level
is bigger and a little slower than the one before. The biggest holds anywhere from a few megabytes to a few tens of
megabytes. When the CPU needs a value, it checks the cache first. If the value is there, that's called a cash hit and
it's very fast. If it isn't there, that's a cash miss. The CPU has to wait while the value comes up from the next
level down or all the way from RAM. Here's the trick that makes the cache work. When the CPU fetches a value from
RAM, it doesn't fetch just that one value. It brings in a whole small block of neighboring bytes along with it. That
block is called a cache line, and it's often 64 bytes. The hardware is betting that you'll want the neighbors next.
Your code doesn't choose what goes into the cache. The hardware handles that by itself, but your code does choose the
order it reads things in, and that order decides whether the hardware's bet pays off. Now, go back to the grid. In many
languages, a grid is stored row after row in memory. Each row follows right after the one before it. Walk it row by
row and each number sits right next to the one before. The first read brings in a whole cache line. The next several
reads are already in the cache. So read after read is a hit and the loop flies. Now walk it column by column. Each step
jumps down to the next row. That's a whole rows worth of numbers further along in memory. The neighbors that came
in with the last read are no help because you won't need them for a long time. So almost every read is a miss and
the loop spends its time waiting on RAM. A plane array keeps its items side by side. So walking it is cash friendly. A
structure where each item points to another item can end up jumping around memory and that often means more misses.
That's one reason the simple array so often beats structures that look better on paper. So, here's a rule of thumb
that works almost everywhere. Nearby is fast and scattered is slow. When you pick how to store data or how to loop
over it, read memory in the order it's laid out. The cache will reward you for it. How can a service crash with a stack
overflow while the machine still has gigabytes of free memory? A running program keeps its data in RAM, but it
doesn't throw everything into one big pile. It uses two main regions, and each has its own rules. They're called the
stack and the heap. The stack is the one that keeps track of function calls. Picture a pile of trays in a cafeteria.
You can only add a tray to the top and you can only take a tray from the top. The stack works exactly like that. Every
time your program calls a function, it puts a new tray on top of the pile. That tray is called a stack frame. It holds
what that one function call needs. It keeps track of where to go back to when the function finishes. and it can hold
the functions parameters and local variables. When the function finishes, its frame comes off the top. That space
is ready to use again straight away. Let's draw it step by step. Say your app shows a customer's profile. The program
starts in a function called main. So the pile has one frame, main. Main calls a function named load customer to fetch
that customer's details. Now there are two frames with load customer on top of main. Then load customer calls parse
email to clean up their email address. Now there are three frames. Main is at the bottom and parse email is on top.
Now let it unwind. When parse email finishes, its frame comes off. Then load customer finishes and its frame comes
off too. You're back to just main. The last call in is always the first one out. That strict order is what makes the
stack so fast. Adding a frame just means moving a marker up. removing it just means moving the marker back down.
There's no searching for free space. That's the picture anyway. In practice, the compiler, the tool that turns your
code into instructions the machine runs, can do better. It may keep some values in registers, the processor's own tiny
storage slots, or it may optimize them away completely. The strict order also has two consequences. First, a
function's local variables vanish when it returns because its frame is gone. Second, the stack has a limited size.
It's often only a few megabytes. That's tiny next to the rest of RAM. So, what happens if calls keep piling up? Say a
function calls itself. That's called recursion. If it never reaches a point where it stops, every call adds another
frame on top. The pile keeps growing until there's no room left. The program crashes with a stack overflow. That's
the crash with gigabytes still free. the stack ran out of room, not the machine. It's also why runaway recursion usually
crashes quickly instead of just hanging. Some languages give you more say in this than others. In C and C++, the way you
declare a variable helps decide whether it goes on the stack. In Java, Python, or Go, the runtime, the engine that runs
your code, makes most of those choices for you. Either way, a long chain of calls that haven't returned yet still
uses up stack space. So, when a crash says Stack Overflow, don't go looking for a memory leak. Look for calls that
go too deep. Often, a recursion that never stops. Here's a bug that has nothing to do with crashing. A service
runs fine, but its memory climbs a little every hour. Nothing seems wrong until someone has to restart it. To
understand that bug, you need the second big region of a program's memory. It's called the heap. The stack handles
function calls. Each call gets a frame, and the frame disappears the moment the function returns. But lots of data needs
to stay around longer than one call. Think of a list that grows as a customer adds items, or a record that a function
loads and then hands back to whoever called it. That kind of data lives on the heap. If the stack is a neat pile of
trays, the heap is more like a big storage room. Your program asks for a space of the right size. It gets back
the address of that space, like a locker number. Then it works with the data at that address. The data stays there until
something releases it. Who releases it depends on the language. In some languages, the program has to free the
memory itself. In others, an automatic helper does it. That helper is called the garbage collector. Every so often,
it finds data the program can no longer reach, and it frees that space. Now, let's see the stack and the heap work
together. Take a function called load customer that loads a customer record. The record goes on the heap with the
customer's name, email, and list of orders. The function's local variable doesn't hold the whole record. It just
holds the record's address on the heap. Now, follow what happens when load customer finishes. First, it hands the
record's address back to main, the function that called it. Then, its frame comes off the stack. Maine keeps that
address in its own variable. The frame came and went, but the record on the heap is untouched. It survives because
Maine still knows where it is. One honest caveat. This is a simplified picture. Different languages decide
where things go in different ways. But the idea holds. Short-lived call data behaves like the stack. Data that grows
or outlives its function behaves like the heap. The heap is flexible, but it has costs. Asking for heap space takes
more work than adding a stack frame. The program has to find a free space and keep track of it. Heap data can also end
up scattered around memory, and scattered data is slower to read because the processor's small, fast memory can't
keep it all close by. The biggest cost is the leak. A memory leak happens when your program holds on to memory it no
longer needs. In languages where you free memory yourself, you might simply forget to. In garbage collected
languages, the collector frees what your program can no longer reach. It can't know what you no longer need. Those
aren't the same thing. So, if something still points to old data, that data stays forever. That's how a leak
happens, even with a garbage collector. Think of a cache that only ever grows and never removes anything. Or an event
listener, a function you ask to run every time something happens, like a click that you never removed. Each one
keeps old data reachable. Memory climbs a little at a time until it becomes a problem. That's the service whose memory
climbs every hour. So when memory keeps climbing, don't look for a crash. Look for something that keeps adding to the
heap and never removes anything. Ask what's still pointing to that old data and why. Almost everyone has written
this bug. You pass a list to a function. Inside the function, you add an item to it. Later, back in your own code, your
list has the extra item, too. Then it goes the other way. You pass a number, change it inside the function, and your
number stays exactly the same. Why does a list behave one way and a number another? To see it, draw three things on
a page. On the left, draw a name tag. That's the variable, the name you use in your code. On the right, draw a box with
the data in it, like a list or a customer record. That's the object, the actual data in memory. Now, draw an
arrow from the name tag to the box. That arrow is the reference. Some languages call it a pointer. Now, two rules fall
out of that drawing. The first is that two name tags can point at the same object. If that object can be changed, a
change through one name shows up through the other. There's still only one object. The second rule is that
assigning a variable or passing it to a function usually doesn't make a new object. Often the new name or the
functions parameter just gets another arrow to the same object. That explains the list bug. The function's parameter
and your variable are two name tags with arrows to one list. When the function adds an item, you see it too. The same
goes for a customer record. Say a function is meant to just format a customer for display, but it quietly
changes the email field. That function has changed your customer. One detail matters here. The function gets its own
copy of the arrow, not your variable itself. So if it points its parameter at a brand new list, your variable doesn't
move. The number case is different. When a function changes a number, it ends up with its own number. In some languages,
it got a copy to begin with. In others, like Python, adding one just points the local name at a brand new number. Either
way, your own variable keeps the old one. Strings work the same way in most popular languages. Changing a string
gives you a new one and the original stays as it was. Let's try a quick test. Make a list called A with three
customers in it. Set B equal to A. Add a fourth customer through B. Take a second and guess what A shows. It shows four
customers. B is just a second name tag with an arrow to the same list. Now give B a brand new empty list and add one
customer to it. What does A show now? It still shows four. Assigning B didn't touch the old list. It just swung B's
arrow over to a new list. A's arrow never moved. The first step changed the object. The second step only moved a
name. Here's an everyday way to hold on to it. Think of sharing a document link versus sending an attachment. Send
someone a link and their edits show up in your document. Send an attachment and they edit their own copy. A reference is
the link. A copy is the attachment. So before you hand an object to a function, decide whether that function is allowed
to change it. If it isn't, give it a copy or give it something it can't change. When a function shouldn't change
your data, the usual fix is to hand it a copy. But a copy can still surprise you. Here's how. You copy a customer record
so you can try out a discount on a draft. In the draft, you lower the prices in the order list. Then you look
at the real customer and the prices changed there too. The record was copied but the order list inside it wasn't. To
see why, draw it out. A variable is a name tag and a reference is an arrow from that name to an object. Copying a
variable usually copies the arrow, not the object. So two names can end up pointing at the same data. Now draw the
customer record as a box. Inside it, there's a name, an email, and an arrow pointing to a second box, the order
list. Make a shallow copy of the record. You get a brand new outer box with its own name and email, but the arrow inside
it is copied as it is, so it still points to the very same order list. Change a price through the copy, and the
original sees it, too. That's the discount bug. Now, make a deep copy. This time, every box gets copied all the
way down. The new record gets its own new order list with its own prices. Change the draft and the original
doesn't move. Many bugs that sound like I copied it and it still changed come down to this. Someone made a shallow
copy when they needed a deep one. What gets copied for you also depends on the language. But the rule underneath is
always the same. Either the data gets copied or only the arrow does. In Java and Python, passing an object copies
only the arrow. So, a function can still change your object. Some languages also have value types like strrus in C,
Swift, and Go. A strruct is a small bundle of fields, and assigning one copies the fields themselves. And in Go,
copying a slice, Go's growable list, or a map, its lookup table still shares the data underneath. So when you're not sure
which kind you have, check your language's rules before you rely on a copy. If you write Python, watch out for
one more trap. Say a function has a parameter whose default value is an empty list. Python builds that list only
once when the function is defined. Every call that doesn't pass in its own list shares that same one. So items added on
one call show up on the next. So a copy is only as deep as you make it. When a function needs its own copy of something
it can change, make that copy yourself and check whether the things inside it need copying, too. That covers the
machine side of your code. Everything starts as bits. A row of switches, each worth double the last, can hold any
whole number up to a ceiling. Make the left switch count as negative, and the same row holds negative numbers, too.
Push a number past that ceiling, and it wraps around or stops with an error. The same bite can be a number, a letter, or
a color, and your program decides how to read it. Text only works when both sides agree on the encoding. And most decimal
fractions can't be stored exactly. So money that has to be exact goes in whole sense or in a decimal type. Where those
bits sit matters just as much. RAM is fast, but it forgets everything when the power goes. Anything that must survive
goes to disk. Data that sits close together is fast thanks to the cache. Function calls use the stack. And data
that has to last usually lives on the heap. And a variable often holds a reference. So two names can share one
object. So when a program surprises you, ask two things. What does this value really represent? And where does it
live? Next comes the other question. How does it grow? Most code works fine on the data you test it with. Maybe that's
a few hundred rows or a handful of users. The trouble starts when the real data arrives and it's a thousand times
bigger. Say a report takes 1 second today. Next year the data is 10 times bigger. Does the report take 10 seconds
or 100? Both are possible. It depends on the shape of the work and you can usually see that shape just by reading
the code. This module teaches you to see it one question at a time. How do you compare two pieces of code fairly? How
do you write down how their work grows? Which shapes of growth are cheap and which are trouble? How do you spot them
in real code? And what about memory? Then come the fixes when growth is too steep, like remembering answers,
sorting, and searching. And at the end are problems that have no fast answer at all. That's the how does it grow
question. Keep it handy because the rest of the course leans on it. So, let's start with why a stopwatch isn't enough.
Here are five numbers. There are 6 3 8 2 and 5. Which one is the biggest? Take a second. It's 8. Now, think about how you
found it. You looked at the first number and kept it in mind as the biggest so far. Then, you checked each next number
against it. When you reached eight, you swapped it in. When you ran out of numbers, eight was your answer. That's
an algorithm. An algorithm is just a clear set of steps that turns an input into an answer. Your code is full of
them. And most jobs can be done by more than one algorithm. So, how do you tell which one is better? Better can mean
easier to read or lighter on memory. Here, the question is speed. The obvious idea is to time them, but a stopwatch
tells you less than you'd think. The same code runs faster on a new laptop than on an old server. one of the
computers that runs a website. Even on one machine, two runs rarely give the same time. And a time for a thousand
records says nothing about a million. So instead of timing the code, count its steps. The number of steps is the same
on every machine. Then ask how that count changes as the data grows. That's called the shape of growth. Here's a
real example. An online store builds a report every night. For each order, it finds the customer who placed it. The
simple algorithm searches the whole customer list from the top for every single order. Start small. With a 100
orders and 100 customers, that's about 10,000 checks. It's over in a blink. Now, the store grows 10 times to a,000
orders and a,000 customers. Before I go on, guess how much more work does the report do? Each order now searches a,000
customers. So that's about a million checks. The data grew 10 times. The work grew a 100 times. Grow it 10 times again
and it's about a 100 million checks. Now the report is slow and a faster server only buys you a little time. Now try a
different algorithm. First put the customers in a lookup table where each customer is filed under their customer
ID like words in a dictionary. Finding a customer then takes about one step. So a 100 orders take about a 100 steps and
10,000 orders take about 10,000. When the data grows 10 times, the work grows 10 times, too. Both algorithms build the
same report. On small data, a stopwatch can't tell them apart, but the first one's work grows with the square of the
data and the second one grows in step with it. Engineers have a short way to write down these shapes. It's called big
O. So when an interviewer asks, "What's the time complexity?" They mean how does the running time grow? So the next time
someone gives you a number of milliseconds, ask the better question. What happens when the data gets 10 times
bigger? Counting steps beats timing. But saying the work grows with the square of the data every time it's tiring fast. So
engineers use a short label instead called big O. It looks like math, but it's really just a name for a pattern.
Here's how to read it. Picture a list of a million names, like a giant contacts list. You want to find one person. Start
with the slowest way. Check the first name, then the next, one at a time until you find them. If you're unlucky, you
check all million. Now, give yourself a list twice as long. You'd have to check twice as many names. The work grows in
step with the length of the list. Here's how engineers write that down. They use the letter N for how big the input is,
meaning the data you give the code. Here N is the number of names on the list. Then they write the pattern as O of N.
The O stands for order, as in the work is on the order of N. Its everyday name is linear because if you drew it on a
graph, it would be a straight line. Other patterns use the same kind of label. O of one means the work stays the
same however long the list gets. O of N squared means the work grows with N * N, like comparing every name with every
other name. Just 10 names already means about 100 comparisons. Big O only cares about what happens when N gets really
big, so it ignores the small stuff. Here's an example. Say you know the person you want is somewhere in the
first half of the list, so you only check the first half. That's twice as fast, which is great. But double the
list and the work still doubles. Half of N is still a straight line, just a flatter one. So it's still O of N. The
same goes for fixed extra work, like 50 steps of setup. Next to a million names, 50 steps are nothing. Making each step
faster speeds you up. But only a different idea changes the shape. Now say a job compares every name with every
other name and then goes through the list one more time. That's n^ 2 steps plus n more. With a million names, n squ
is a million * a million. That's a trillion. The extra pass adds just 1 million. Next to a trillion, a million
is like one extra page on a stack of a million pages. You'd never notice it. So that's O of N squared. Keep the part
that grows fastest and drop the rest. Try one yourself. A job goes through every customer once to tidy up their
details. Then it goes through them all again to check their emails. Last, it grabs the very first customer on the
list. What's the big O? Pause and work it out. Two full passes are 2 N. Grabbing the first customer is one step,
so that's 2 N + 1. Drop the small stuff and the answer is O of N. Two passes take twice as long, but the shape is
still a straight line. One more thing, the same search can be lucky or unlucky. The name you want might be first on the
list. That's the best case. Or it might be last. That's the worst case. Stopping as soon as you find the name is a good
habit, but it doesn't help when the name is last. So when people give a big O without saying which case, they usually
mean the worst one. If you're not sure, ask. So when someone reviewing your code writes O of N squ, they aren't giving
you a grade. They're telling you what will happen when N gets big. Now you can read a label like O of N. The next
question is which labels are good news. Three of them are. When data grows, these jobs barely notice. They're the
cheap growth shapes. To see them, take a customer list and let it grow from a thousand customers to a million. Then
watch how much work three everyday jobs take. The first job is to get the customer at position 500. Think of a row
of numbered lockers. If you know the locker number, you walk straight to it. You don't open every locker before it. A
list works the same way. The computer jumps straight to position 500. That's one step for a thousand customers and
still one step for a million. That shape is written O of one and it's called constant. The size of the list doesn't
matter at all. The second job is to find one customer by name in a list sorted by name. Think of looking up a word in a
dictionary. You open near the middle. If your word comes later, you ignore the first half. Then you open the middle of
what's left and repeat. Each look throws away half of what's left. This is called binary search. So how many looks does it
take for a th000 customers? Pause and guess. It's about 10. 1,000 halves to 500, then 250, and so on down to one in
about 10 steps. For a million customers, it's only about 20. That shape is written O of log N, and it's called
logarithmic. The list grew a thousand times, but the work only doubled. That difference beats raw speed. Say you
check names one at a time on a computer 100 times faster and use having on an old laptop. With a 100 names, the fast
computer wins easily. But with a million names, the fast computer still takes as long as 10,000 of the laptop steps,
while the old laptop needs only 20. Past a certain size, the better shape always wins. The third job is to find the
biggest spender. This time, there's no shortcut. Think of a teacher finding the top score in a pile of tests. They have
to look at every test once and remember the best so far. For a thousand customers, that's a thousand steps. For
a million, it's a million. That shape is written O of N, and it's called linear. When the list doubles, the work doubles.
All three are cheap in practice. Even linear is fine for most jobs because you usually have to look at the data at
least once anyway. But when you can use a sorted list or jump straight to a position, you can skip almost all of
that work. So, here's what to take away. Constant doesn't grow. logarithmic barely grows because it has the work at
every step and linear grows in step with the data. Those three shapes stay cheap however big the data gets. The other
three don't. These are the expensive growth shapes. With them, code can be fast in testing and very slow on real
data. Take the same growing customer list and run three harder jobs on it. The first job is to sort the list by
spending. Think of sorting a tall stack of exam papers by score. A good method splits the stack into smaller piles,
sorts those, and merges them back together. For a thousand customers, that takes about 10,000 steps. For a million,
it takes about 20 million. That shape is written O of N login. It's a little worse than linear, but not by much. It's
the shape of good sorting. The second job is to find customers who share the same address. The simple way compares
every customer with every other one. Think of a room where every person shakes hands with every other person.
Four people make six handshakes. 10 people make 45. 100 people make nearly 5,000. When the group doubles, the
handshakes go up about four times. Now apply that to the customer list. Pause and guess. For a million customers, a
thousand customers means about half a million comparisons, which is fine. A million customers means about half a
trillion, which is far too slow. That shape is written O of N squared, and it's called quadratic. In code, it
usually looks like a loop inside a loop. The third job is the worst. Marketing wants to test every possible combination
of their discount offers. Here, N is the number of offers, not customers. Think of a row of light switches. Each new
switch doubles the number of ways you can set them. One switch gives two settings. 10 switches give about a
thousand. 20 give about a million. 30 give about a billion. That shape is written O of 2 to the N and it's called
exponential. It becomes too slow after just a few dozen items. So here's what to take away. N log N is the price of
good sorting and it's fine. Quadratic is fine for small lists and far too slow for big ones. and exponential is only
usable when n stays tiny. You now know the six shapes by name. The useful skill is spotting them in your own code
without running it. Think about checking guests at a party. If each guest shows their invitation once at the door, the
work grows with the number of guests. But if every guest has to be introduced to every other guest, the work grows
much faster. Code has the same two patterns. The clues are in the loops. Start with single lines. Adding two
numbers, comparing two values, storing a value, or reading the item at a known position each take one step. They cost
the same whatever the numbers are. Now, the simplest rule for loops. One loop over the data means linear. If a list
has n items and the loop visits each one once, that's n steps. Now, put a loop inside that loop, both over the same
data. For every item, the inner loop visits every item again. That's n * n or quadratic. Now put the two loops side by
side instead, one after the other. The first loop takes n steps. Then the second loop takes n more. That's 2 n,
which is still linear. So here's the rule to remember. Loops one after another add. Loops one inside another
multiply. There's one catch. That rule assumes both loops go over the same data. Say one loop goes over the
customers and the other over the orders. Those are different sizes, so give them different letters a and b. Side by side,
that's a + b. Nested, it's a * b. Only call it n squ when both lists grow together. Those rules work most of the
time, but code can trick you. So count how many times the work really happens, not the loops. Here's a loop that looks
linear but isn't. The counter starts at 1 and doubles each time until it passes n. So it goes 1 2 4 8 and so on. For a
million, it stops after about 20 rounds. That's login, not n. And here's one that looks linear but is constant. A loop
that always runs exactly 10 times, however big the data gets, is one fixed chunk of work. So it's O of one.
Now test your eye. Here are three short cases. Guess each one before I answer the first one. A function goes through
every customer. For each one, it checks whether their email is in a list of blocked emails. What's the shape?
There's only one loop you can see. But checking whether an email is in a list is a hidden loop. Behind that one line,
the computer walks the whole blocked list each time. So the work is n * the size of that list. If both lists grow
together, that's quadratic. Now, store the blocked emails in a hash set, a collection built for fast lookups. Each
check takes about one step, and the whole thing becomes linear. The second one, a function loops over every
customer to check their address. Then, in a separate loop, it goes over every order to check its total. What's the
shape? The two loops sit side by side, so their work adds, but they go over different lists. So it's a + b where a
is the number of customers and b is the number of orders. The third one for each customer an inner loop compares them
only with the customers after them in the list. So the inner loop gets shorter every time. Is that cheaper than
quadratic? It's about half the work. But as you saw earlier, having the work doesn't change the shape. It's still n
squ. So when something is slow, find its shape first. If it's quadratic, look for the loop inside a loop. Then ask whether
a hash set or a lookup table can replace the inner loop. That one change often turns n^ squ into n. Every shape so far
has measured time. But code also uses memory, and memory can run out first. Here's how that looks. Say a store runs
a small program every night while the shop is closed. It opens a file listing the day's orders and works through them.
On a small test file, it runs fine. Then the real file arrives 100 times bigger. The program doesn't get slow. It crashes
with an out of memory error. It simply needed more memory than the machine had. So besides asking how the time grows,
you can ask how the memory grows. That's called space complexity, and it uses the same big O shapes. Usually you count
only the extra memory a job needs on top of the data it was given. That extra memory comes from new values, new lists,
and even function calls because each call that's still waiting holds its own details in memory. Think about working
at a desk with a stack of order forms. Some jobs need just a sticky note. Some need a photocopy of every form, and some
need a chart as big as a wall. The sticky note job is adding up the total of every order. You keep one running
total, and that's it. It's one number whether there are 10 orders or 10 million. That's O of one space. The
photocopy job is making a cleaned up copy of every order. The copy is as long as the original. Double the orders and
you double the memory. That's O of N space. The wall chart job is comparing every order with every other order and
writing down each result. That's one box for each pair. A million orders means a trillion boxes. That's O of N squared
space and it won't fit on any normal machine. Often you can trade memory for time. Say you want to know whether any
order number appears twice. One way is to compare every order with every other. That's slow, but it needs no extra
memory. The other way is to walk the stack once and keep a hash set of the order numbers you've already seen.
That's fast, but the set grows with the data. You've bought time with memory. The right choice depends on which one
you're shorter of. Try one. A function needs the 10 earliest orders. It photocopies the whole stack, sorts the
copy by date, and takes the first 10. How much extra memory does that use? Pause and think. The copy is as big as
the stack. So that's O of N extra space. Here's a better way. Walk the stack once and keep just 10 slots for the earliest
orders seen so far. The memory is 10 slots whether there are a thousand orders or a million. That's O of one
extra space on the huge file. That's the difference between crashing and finishing. So here's what to take away.
Memory has a shape, too. Before you copy everything, ask whether a sticky note would do. Time and memory can both go
wrong in one line of code that looks simple. Here's a trap that catches almost everyone and it hides in very
ordinary code. Say you're building a report one line at a time. You start with an empty string, then you add a
line, then another a thousand times. It looks like a simple linear job. Often it isn't. To see why, picture writing a
letter by hand with one strange rule. You're not allowed to add to a page. To add a line, you must copy everything
you've written so far onto a fresh sheet. Then you write the new line at the bottom. The first line is easy. You
copy nothing and write one line. For the second line, you copy one line, then write one. For the third, you copy two,
then write one. By the last line, you copy almost a thousand lines just to add one more. How much copying is that in
total? Pause and guess. Add it all up and it's about half a million lines copied just to produce a thousandline
letter. That's quadratic work for what felt like a simple job. Double the report and the copying goes up about
four times. That strange rule is how strings work in many popular languages. Once a string is made, it can't be
changed. That's called immutable. So adding to a string really means making a brand new longer string and copying the
old one into it. Some languages quietly speed this up, but you can't count on it. The fix is to change the habit.
Write each line on its own card first. When you're done, put all the cards together into one string at the end.
Each line gets copied about once, so the work is linear. In code, that means collecting the pieces in a list and
joining them at the end. Python has a join for this. Java and C have a tool called string builder that does the same
job. So, here's what to take away. When you build something up inside a loop, ask what each step really copies. A line
that looks cheap can quietly copy everything that came before it. Every example so far has been a loop over a
list. But some problems are shaped like a tree with pieces inside pieces. Loops find those hard. Recursion makes them
easy. Say you need to count every file in a folder, including all the files in its subfolders. One level is easy. You'd
write one loop. But subfolders have their own subfolders, and you don't know how deep they go. So, how many loops do
you write? You don't need more loops. You write one function that counts the files in this folder, then calls itself
on each subfolder. A function that calls itself is called recursion. Every recursive function has two parts.
The first is the base case. That's the simplest version of the problem where the answer is obvious. Here it's a
folder with no subfolders. The function just returns its own file count. The second part is the recursive case. The
function does a little work then calls itself on something smaller. Here it counts its own files, then adds whatever
each subfolder sends back. This runs on the call stack, the pile of trays from earlier. Each call gets its own tray
holding details like which folder it's working on. When a call finishes, its tray comes off and the call underneath
carries on from where it paused. Now, let's trace a tiny example. The top folder holds two files and two
subfolders, A and B. Folder A holds three files and nothing else. Folder B holds one file and one subfolder C and C
holds four files. The call for the top folder counts its two files. Then it calls itself on A and waits. A has no
subfolders, so it's a base case. It sends back three. The top call picks up again and calls itself on B. B counts
its one file, then calls itself on C and waits two. At this moment, three calls are on the pile. The top folder is at
the bottom. B is in the middle and C is on top. C is a base case, so it sends back four. B adds its own one and sends
back five. The top call adds its own two plus three from A plus five from B. The answer is 10 files. Notice the pile was
never taller than three trays. That's one for each level of folders. So the memory recursion uses grows with how
deep it goes. And that's it. One danger. If something is nested too deeply or the base case is missing, the pile keeps
growing until there's no room left. Then the program crashes with a stack overflow. You can always rewrite
recursion as a loop by keeping your own list of work still to do. That avoids the pile's size limit. But for nested
things like folders, menus, or comments with replies, the recursive version is usually shorter and easier to get right.
So when you don't know how deep something goes, don't count the levels. Let each call handle one. Recursion
makes some problems easy to write. But written the obvious way, it can also do the same work again and again. Here's a
puzzle that shows it. Picture a staircase with six steps. You can climb one step at a time or two at a time and
mix them however you like. How many different ways are there to reach the top? Start small and count. With one
step, there's one way. With two steps, there are two ways. You can take two single steps or one double step. Now try
three steps. Pause and count them. There are three ways. You can go one, one, one, or one then two or two then one.
Here's the idea that makes the rest easy. Think about your last move. To stand on step three, you either came
from step two with a single step or from step one with a double step. So the ways to reach three are the ways to reach two
plus the ways to reach 1. 2 + 1 is 3 and it matches. That rule works for every step. The ways to reach six are the ways
to reach 5 plus the ways to reach four. That's easy to write as a function that calls itself. It asks for five and for
four and adds them up. That function is correct, but it's wasteful. To work out six, it asks for five and four. But to
work out five, it asks for four again. So four gets worked out twice. Three gets worked out three times. Two gets
worked out five times. For just six steps, the function makes 15 calls to answer six different questions. It gets
much worse as the stairs grow. Each call splits into two more calls and most of them repeat work that's already been
done. For 50 stairs, it would make tens of billions of calls. That's exponential growth. The fix is almost too simple.
Write the answers down. Keep a small notebook with one entry for each number of stairs. In code, that's a hashmap,
like a dictionary. Before working anything out, the function checks the notebook. If the answer is there, it
uses it. If not, it works it out once, writes it down, and moves on. Now, each question is answered only once. Six
stairs takes six real calculations. 50 stairs take 50. The exponential growth has become linear. The price is a little
memory for the notebook with one entry per step. Writing answers down like this is called memoization. It's one form of
a technique called dynamic programming. That's a fancy name for a simple idea. Build a big answer from smaller ones and
never work the same one out twice. So, how do you know when to use it? Look for two signs. First, the answer can be
built from answers to smaller versions of the same problem. Second, those smaller versions keep showing up again
and again. That second sign is called overlapping subpros. When a recursive function keeps asking the same
questions, write the answers down. Writing answers down is one way to stop recursion from repeating itself. There's
a second way, and it doesn't need a function that calls itself at all. Take the same staircase puzzle with six
steps. You already know the rule. The ways to reach any step are the ways to reach the two steps below it added
together. This time, start at the bottom and work up. Draw a row of six boxes, one for each step, and fill them in from
the left. Step one has one way. Step two has two ways. Step three is 2 + 1, so three. Now try step four yourself. Pause
and add the two boxes before it. It's 3 + 2, so 5. Step five is 5 + 3, so 8. And step six is 8 + 5, so 13. There are 13
ways to climb six steps. Notice what didn't happen. Nothing was worked out twice and no function called itself. So
there's no pile of waiting calls that could overflow. Filling a table from the smallest case up like this is called
bottomup dynamic programming. Now look at the boxes again. Each one only needed the two boxes right before it. So you
don't need the whole row. You can keep just two numbers and slide them forward as you go. The time still grows in step
with the number of stairs, but the memory stays the same. however tall the staircase gets. This pattern shows up in
real apps, too. Say a customer types JHN into a search box. To suggest John, the app works out the fewest single letter
changes that turn one word into the other. Here, that's one change, adding the missing O. That number is called the
edit distance. It's worked out by filling a table, just like the staircase. Each box answers the question
for slightly shorter pieces of the two words. Spell checkers and did you mean
suggestions work the same way. There's one catch. Saving answers only helps when the same smaller questions come up
more than once. Take merge sort, which sorts a list by splitting it in half, sorting each half, and merging them. It
never sorts the same piece twice. So, a table of saved answers would just waste memory. So, here's a simple test. If a
slow recursive function keeps asking the same questions, fill a table from the bottom up instead. Remembering answers
is one way to cut the work. Putting data in order is another, and plenty of everyday features needed anyway, like
leaderboards, reports, and sort by price buttons. Here's what goes wrong when it's done the simple way. A dashboard, a
page of charts and numbers for the store's team, has a sort by spend button. In testing with a few hundred
customers, it's instant. With a million real customers, the page freezes. Someone wrote the sort by hand. The
simple way. Let's look at the simple way first. Walk through the list and compare each pair of neighbors. If they're in
the wrong order, swap them. After one full pass, the biggest number has moved to the end. Then do another pass and
another until nothing needs swapping. This is called bubble sort because the big numbers bubble up to the end. How
much work is that? Each pass compares about n pairs and you may need about n passes. That's n * n or quadratic. A
thousand customers take about a million steps. Before I go on, guess what would a million customers take? It's about a
trillion steps. That's the frozen button. The fast way uses a different idea. Split the list in half. Sort each
half. Then merge the two sorted halves together. And how do you sort each half? The same way. By splitting it again.
This is called merge sort. Let's watch it on eight numbers. They're 5 2 7 1 6 3 8 and 4. Keep splitting until every
piece is a single number. A single number is already sorted. Now merge neighbors into sorted pairs. You get 2
and 5, then 1 and 7, then 3 and 6, then four and 8. Next, merge the pairs into fours. You get 1 2 5 7 on the left and 3
4 6 8 on the right. Last, merge those two. Compare the front numbers each time and take the smaller one. That gives 1,
then 2, then three, and so on up to eight. Now count the rounds of merging. There were pairs, then fours, then all
eight. That's three rounds. Three is how many times you can have eight before you reach one. That's what log n means. And
in each round, every number gets looked at once. So each round is n steps. Log rounds of n steps gives n log n. For a
million customers, that's about 20 million steps instead of a trillion. The button stays instant. There's another
fast way called quicksort. It picks one item called the pivot. It moves everything smaller to one side and
everything larger to the other. Then it does the same to each side. It's usually very fast, too, but an unlucky choice of
pivot can make it slow. You'll rarely write any of these yourself. The sort that comes with your language already
uses a fast method like these, so use it. And for sorts that work by comparing items, n login is a proven limit. No
clever trick can beat it. One last warning. If you sort inside a loop, you pay for a full sort every time around.
So, sort once before the loop. Sorting has a big payoff. Once data is in order, finding things in it gets much faster.
Say a website has to check whether a customer ID exists every time someone loads a page. It checks a list of a
million IDs. Checking them one by one means up to a million checks every single time. But the list is sorted and
that changes everything. It lets you use binary search, the having trick you met with the dictionary. Here's how it works
in detail. Look at the middle item. If it's the one you want, you're done. If it's smaller than what you want, the
answer can only be in the right half. So, drop the left half. If it's bigger, drop the right half. Then, repeat on the
half you kept. Each step cuts the list in half. So a million items take about 20 steps. That's O of log N. Let's trace
it. Take 16 sorted numbers that count up in threes. They go 3 6 9 and so on up to 48. Number positions from 0 to 15.
You're looking for 39. Before I trace it, guess how many steps it'll take. Keep two markers called low and high.
Low starts at position zero and high at 15. The middle is position 7. It holds 24, which is too small. So move low up
to 8. Now the middle is position 11. It holds 36. Still too small. So move low up to 12. The middle is now position 13.
It holds 42, which is too big. So move high down to 12. Now low and high are both 12. Position 12 holds 39. You found
it in four steps. There's one rule you can't skip. The list must be sorted. On an unsorted list, binary search doesn't
just get slow. It gives wrong answers. Throwing away half is only safe when the answer can't be in that half. That leads
to a trade. Sorting a list takes some work up front. After that, searching an unsorted list takes n steps every time.
But searching a sorted list takes only login. So if you'll search just once, don't bother sorting. If you'll search
many times, sort once. And every search after that is fast. That's why so much real data is kept sorted or indexed,
which means organized ahead of time for fast lookups. Binary search is easy to describe, but famously easy to get wrong
in code. The classic mistake is in moving the markers. Low must move to just past the middle and high to just
before it. If low only moves to the middle itself, the search can get stuck and loop forever. Small slip ups like
that are called off by one errors. So if your language already has a binary search or a sorted lookup, use it. The
idea is simple. The details are where the bugs hide. Every slow problem so far had a faster method waiting to be found.
Some problems don't. It pays to recognize those before you spend a week looking. Here's a feature request that
comes up again and again. A web app sells to local customers. Each morning, one driver leaves the warehouse with 20
orders to drop off. The product manager, the person who decides what the app should do, wants the app to plan the
best route, not just a good one. It sounds like a weekend task, but it's one of the most famous hard problems in
computer science. Let's follow that one driver and see why. Start with the obvious idea. Try every order of the
stops and keep the shortest. This is called brute force and it's guaranteed to be right. So, how many orders are
there? Any of the 20 stops can go first. Any of the 19 left can go second, then 18 all the way down to one. That's 20
factorial. About 2.4 quintilion orders. Check a billion orders every second and you finish in roughly 77 years. That's a
factorial shape. It grows even faster than exponential. Add a 21st stop and the work multiplies by 21. No hardware
fixes this shape. A thousand servers only buy a couple more stops. So people reach for a shortcut. The obvious one is
to always drive to the nearest stop you haven't visited yet. That's called a greedy algorithm. At each step, take
whatever looks best right now and never reconsider. It's fast, and on real maps, it's usually decent, but it isn't always
right. Here's a tiny case where it goes wrong. The warehouse sits on a straight road. The driver doesn't need to come
back at the end. Stop A is 1 mile east. Stop B is 2 m west, and stop C is 5 m east. The greedy driver goes to A first
since it's closest. That's 1 mile. From A, B is 3 m away and C is 4. B is closer, so the driver heads west to B.
That's three more miles. Then from B, it's 7 m all the way out to C. 1 + 3 + 7 makes 11 m. Before I show the better
plan, look again. Can you find a shorter route? Take a second. Now try the better plan. Go west to B first. That's 2 m.
Then drive east. It's 3 miles to A and four more on to C. 2 + 3 + 4 makes 9 miles. Grabbing the closest stop first
cost two extra miles. That doesn't mean you should never trust greedy. Sometimes there's a proof that it's the best you
can do. Map apps use a greedy method to find the shortest path between two places. It's called Dystra's algorithm,
and there's a proof that it always finds the best path. Making change is greedy, too. You hand over the biggest coin that
fits and repeat. For common coin systems like US coins, that always uses the fewest coins. But that's a property of
those particular coins, not of every coin system. Say you invent coins worth 1, three, and four. Then you ask for
six. Greedy hands over a four, then a 1, then another one. That's three coins in all. 3 + 3 needs only two. So the
question is never is greedy allowed. It's is there a proof that greedy is right here? That delivery route belongs
to a whole family of hard problems. The best way to see why it's hard is to compare it with a problem that sounds
almost the same but isn't. Here's the setting again. One driver leaves the warehouse each morning with 20 orders to
drop off. The product manager asks for two features. The first feature finds the shortest drive from the warehouse to
one customer. The second finds the best order to visit all 20 stops. Before going further, take a guess. Which one
is hard? Start with the first. Picture the streets as a grid of corners. Work outward from the warehouse. For each
corner, keep the shortest distance you've found so far. Each time, pick the closest corner you haven't settled yet
and settle it. Once a corner is settled, its distance never changes again. So each corner is handled about once. Even
for a whole city, a map app does this in under a second. Now try the second on a tiny scale. With three stops, A, B, and
C, how many orders can you visit them in? Pause and count. There are six. You can start with A and go A, B, C, or AB.
You can start with B and go B A C or BCA. Or you can start with C and go C A B or CBA. Add a fourth stop and there
are 24 orders. With five stops, there are 120. Each new stop multiplies the count. With 20 stops, you get the 2.4
quintilion orders from before. And here's why there's no easy shortcut. On the map, you could settle one corner and
move on. With the stops, you can't. Where you put one stop changes the cost of every choice after it. A choice that
looks good early can ruin the route later. So, the first problem is easy and the second is hard. Problems like the
best delivery route are called NP hard. They belong to a big family of hard problems. For every one of them, nobody
knows a fast way to always find the best answer. And they're linked. So, a fast way to solve one would solve them all.
Many scheduling problems are in this family and so is packing items into boxes. So what do you tell the product
manager? First, recognize the shape. When a problem asks for the best order, the best group, or the best arrangement
out of many, suspect this family. Stop hunting for a perfect fast method and pick one of three moves instead. If the
input is tiny, say 10 stops, just try every order. If it's bigger, use a heristic, a method that finds a strong
answer without proving it's the best, and give it a time limit. Or hand the problem to a solver library, a
ready-made tool built for these problems. It combines clever search with heristics. That's what real root
planning software does. It promises a very good route, not a perfect one. So when a problem asks for the best of a
huge number of choices, don't chase perfect. Ask for good enough. within a time limit that covers how work grows. A
stopwatch tells you about one run. The shape tells you what happens when the data gets bigger. Big O is just a short
name for that shape from constant and logarithmic through linear and n login up to quadratic and exponential. You can
spot the shape by reading the loops. Loops one after another add and loops one inside another multiply. Memory
grows too, so watch for copies built up inside a loop. Recursion handles nested problems with each call waiting its turn
on the stack. When it keeps asking the same questions, write the answers down or fill a table from the bottom up. The
fast way to sort takes n login and once data is sorted, binary search finds anything in a handful of steps. Some
problems like the best delivery route have no known fast answer. For those ship a very good answer within a time
limit. So when code gets slow as the data grows, ask one thing first. What's its shape? Next come data structures.
They decide how much of this work your code has to do. Every program keeps collections of things. Think of a list
of orders, a line of emails waiting to go out, or the history behind an undo button. This module starts with what a
data structure is. Then it covers the simplest ones, the ones that keep items in a line. Those are arrays, linked
lists, stacks, and cues, plus two everyday tricks for working through arrays. For each one, you'll see what's
cheap, what's expensive, and why. That brings both questions together. How does it grow? Where does it live? So, let's
start with a small shop and the different ways it keeps things. You've just spent a module measuring how work
grows. Here's something that may surprise you. Very often, how fast the job runs depends more on how the data is
arranged than on the code itself. Think about a small shop. It keeps things in several different ways, and each way
suits one job. Parcels waiting for pickup sit on a shelf with numbered spots. When a customer says spot 214,
you walk straight to it. You don't check the spots before it. Shopping baskets sit in a stack by the door. Each
returned basket goes on top, and each new customer takes one off the top. The last basket in is the first one out.
Customers wait in a line at the checkout counter. The first one to arrive is the first one served, and new people join at
the back, and the delivery driver follows a chain of notes. Each note gives one address and says where to find
the next note. To reach the fifth stop, you have to follow the first four notes. Each of those is a way of arranging
things. In code, a way of arranging data is called a data structure. Put simply, it's some values arranged in a certain
way. It comes with rules for adding, removing, and finding them. No arrangement is fast at everything. Try
it. Which arrangement is best for get me the parcel in spot 214? And which is best for serve whoever has waited
longest? Pause and decide. The numbered shelf wins the first job. You go straight there in one step. The line
wins the second because the person at the front is always the right one. But ask the line for its 214th person and
you have to count down the line. And ask the shelf who arrived first and it has no idea. That's why there are many data
structures, not one best one. Each makes some jobs cheap and others expensive. Most of those jobs come down to a short
list. You add an item, you remove an item, you find an item, you get the item at a certain position, and you go
through every item once. Every data structure has a big O cost for each of these jobs. There's also a reason
underneath in memory. Memory is a long row of numbered slots. Some structures keep their items side by side in that
row, like the numbered shelf. Others scatter them with each item pointing to the next, like the chain of notes. That
one choice, side by side or scattered, explains most of what a structure is good and bad at. The good news is that
you rarely build these yourself. Your language already gives you most of them, like lists, dictionaries, and sets. The
skill isn't building them. It's knowing which one to pick. So, here's what to take away. A data structure is a way of
arranging data so that some jobs are fast. Before you pick one, ask which jobs you'll do most often. The numbered
shelf from the shop has a name in code. It's called an array. In most languages, it's what sits underneath a list. You
add items to the end, which is called appending, and you read them by position. Here's a puzzle about it. Say
a program keeps a log. That's a running list of everything that happens. It adds a million entries to it, one at a time.
Almost every ad is instant. But every so often, one ad takes a noticeable pause. Meanwhile, reading entry 500 is always
fast, however big the list gets. Both of those come from how an array is built. An array is a block of memory split into
equal slots one after another with nothing in between. For simple values like numbers, each slot holds the value
itself. For objects, a slot holds a reference, an arrow to where the object really lives. Because the slots are
evenly spaced, finding any position is simple arithmetic. Try it. Say the array starts at memory address 1,00 and each
slot takes 8 bytes. Counting from zero, where does the item at position three sit? Pause and work it out. It's 1,00 +
3 * 8. That's 1,024. The computer does the same sum for position 500 or position 5 million.
That's O of 1. And because the slots sits side by side, the cache helps too. When the computer reads one slot, it
brings the neighbors along. So walking an array from start to end is very fast. Now the weaknesses. The block has a
fixed size chosen when it's created. Think of the shop's shelf when every spot is full. To add one more parcel,
you need a bigger shelf. You set it up, move every parcel across, and then add the new one. For an array, that move is
a copy of every item. That's O of N. If the array grew by just one slot each time, every ad would trigger a full
copy. Adding N items would then be quadratic, O of N squared. So growable lists plan ahead. When the block fills,
they grab a much bigger one, often 1 and 1/2 or two times the size. Here's one to guess. Starting small and doubling each
time, how many copies happen while you add a million items? Take a second. Only about 20. Each copy is bigger than the
last. But add them all up and it's about 2 million moves in total. That's only about two moves for each item. Most ads
land in spare room and cost almost nothing. Engineers call that amortized, which just means spread out, like paying
for something in small monthly payments instead of all at once. So adding to a list is amortized O of one. Those rare
copies are the pauses in the log. The other weakness is the middle. To squeeze a parcel into spot three, every parcel
after it has to move down one spot. The array works the same way. Inserting or deleting anywhere except the end is O of
N. There's one more mistake that almost everyone makes. Say you loop through a list and remove the items you don't want
as you go. When you remove one, everything after it shifts down a slot, so the loop skips the item that just
moved into place. Some languages stop with an error instead. The safe fix is to build a new list of the items you
want to keep or to loop over a copy. So, here's the profile. Reading by position is fast. Walking in order is fast.
Adding at the end is cheap on average. Inserting or deleting in the middle is slow. That's why a list built on an
array is the default in nearly every language. When you're not sure what to use, start with one. The array's biggest
weakness is the middle. Inserting there means shifting everything after it. The obvious fix is a structure that never
has to shift. It's the delivery driver's chain of notes from the shop. And in code, it's called a linked list. Each
note holds one item plus where to find the next note. In code, each note is called a node. It lives in its own small
chunk of memory wherever there was room. The node holds the item and a pointer, a reference to the next node. You hold on
to the first node and it leads you to the rest. That makes inserting easy. Say you want a new stop between stop two and
stop three. You write a new note and make it point to stop three. Then you change stop two to point to the new
note. Nothing else moves. That's O of one. Removing a stop is just as easy. You make the stop before it point past
it. But there's a problem. To insert after stop two, you first have to get to stop two. And the only way there is to
follow the chain from the start. There's no arithmetic to jump to position 500 the way an array does. You follow 500
pointers. So reaching a position is O of N. There's a memory cost too. Every node carries at least one pointer as well as
its item. For small items like numbers, those pointers can take as much memory as the items themselves. An array stores
just the items. Here's a common surprise. A textbook says linked lists win for inserts. Your code inserts into
the middle of a list all the time, so you switch. Then you run a speed test and it's slower. What happened? Take a
guess. The insert itself really is O of one. But to reach the middle, the code had to follow hundreds of pointers. And
because the nodes are scattered around memory, many of those jumps miss the cache. The array, meanwhile, shifts its
items in one fast sidebyside copy, which the cache handles well. The walk to the spot is where the linked list lost. So
the linked list only wins when you already hold the node you want to change. The very front of the list is
one example. Then there's no walk at all. There's also a version where each node points both ways, forward to the
next and back to the one before. It's called a doubly linked list. It costs a second pointer in every node. In return,
you can walk it in either direction, and you can remove a node when that node is all you have. Linked are still worth
knowing. They're used inside other structures like some hashmaps and caches. interviews use them to test
whether you understand pointers and nodes that point to other nodes are the starting point for trees and graphs
which come later in the course. So in theory, the linked list wins for inserts. On real hardware, the array
usually does. So use an array by default. Arrays and linked lists let you reach any item. Sometimes that's more
freedom than you want, and a strict rule works better. Think about the stack of shopping baskets by the shop's door. The
basket you pick up is always the last one someone put back. That's a stack. The rule is that the last thing in is
the first thing out. Engineers write that as LIFO for last in first out. A stack has three moves. Adding to the top
is called push. Taking from the top is called pop. And looking at the top without taking it is called peak. All
three are O of one because everything happens in one place. Here's where that rule is exactly right. How would you
build undo for a text editor? Say the user types a word, then deletes a line, then pastes a paragraph, then they press
undo. Which change should come back first? Take a second. It's the paste because it was the most recent. Press
undo again and it's the delete. You always need the newest change first. So each edit is pushed onto a stack and
undo pops the top. A browser's back button can work the same way. Here's another one worked by hand. You want to
check whether the brackets in some code are balanced. Every opening bracket needs a matching closing bracket in the
right order. Take an opening parenthesy, an opening square bracket, a closing square bracket, and a closing
parenthesy. Push the opening parenthesy. Push the opening square bracket. Now the closing square bracket arrives. Pop the
top. It's an opening square bracket, so it matches. Then the closing parenthesy arrives. Pop the top. It's the opening
parenthesy. Another match. The stack is empty at the end, so the brackets are balanced. Now try one yourself. An
opening parenthesy, then a closing square bracket. Balanced or not? Pause and work it out. It's not balanced. You
push the opening parenthesy, then the closing square bracket pops it and finds the wrong kind. Brackets also fail if a
pop finds the stack empty or if anything is left over at the end. You've already met the most important stack of all.
It's the call stack, the pile of trays from earlier. Each function call pushes a frame and each return pops one. That's
why the most recent call always finishes first. The call stack is memory the language manages for you and it's small.
A stack you make yourself follows the same rule, but it usually lives on the heap, so it can grow much larger. That's
why a very deep recursion can be rewritten as a loop with your own stack. Inside, a stack is usually just an
array. Push adds to the end and pop removes from the end. Both are cheap and you get the array's speed, too. So,
whenever a problem needs the most recent thing first with older things waiting their turn, use a stack. stack always
serves the newest item first. A lot of real work needs the opposite. Think about the line at the checkout counter.
New customers join at the back and the one at the front is served next. That's a Q. The rule is that the first thing in
is the first thing out written FO. It's a rule about fairness. Whoever has waited longest goes next. A Q has two
moves. Adding to the back is called NQ. Taking from the front is called DQ. Both should take about one step. Here's where
that matters. On launch day, a thousand people sign up in one minute. Each one should get a welcome email in the order
they signed up. But nobody should wait on a loading page while their email is sent. So the sign up page adds an email
to a queue and finishes right away. A separate program called a worker takes jobs from the front one at a time,
oldest first. The Q holds the whole rush and keeps everything in order. Now, how would you build a Q? The obvious idea is
an array. Adding to the back is easy because it's just an append. But what happens when you take from the front?
Pause and think. Every item has to shift forward one slot. That's O of N every single time. For a long Q, that's slow.
So, real Q's are built differently. One way is a linked list where removing the front is just a pointer change. The
other is a circular array. Picture the array's slots arranged in a ring like seats around a table. The Q keeps two
markers, one for the front and one for the back. Taking from the front just moves the front marker one seat along.
Adding moves the back marker. When a marker reaches the last seat, it wraps around to the first. Nothing ever
shifts. Most languages give you a ready-made queue built in one of these two ways. So use it. There's one
warning. If work keeps arriving faster than the worker can handle it, the queue just keeps growing. So real systems put
a limit on the queue or ask senders to slow down. Q's also shape how programs explore. Say you're looking through a
network of friends level by level. First you visit all of your friends, then all of their friends. A Q remembers who to
visit next in order. That's called breadth first search. It finds the shortest path counted in steps from one
friend to the next. Use a stack instead and you dive down one path first. The structure you choose decides the order.
You'll also hear about two related structures. A DQ, pronounced deck, is short for double-ended Q. It lets you
add and remove at both ends. A priority Q serves the most important item first instead of the oldest. So a Q is oldest
first. Good for fairness and for working through a rush in order. Use the wrong one of the two and the bug is easy to
spot. You get an undo button that brings back your oldest change or welcome emails that go out newest first. Arrays
are simple, but a lot of slow code runs a loop inside a loop over the same array. Two everyday tricks turn many of
those quadratic jobs into a single pass. They're called twop pointers and the sliding window. Start with two pointers.
Say a shopper has a gift card worth $43 and wants two items that use it exactly. The prices are sorted from cheapest to
most expensive. They're 5 12 18 25 32 and $45. The obvious way is to try every pair,
which is quadratic. For a catalog of 10,000 items, that's about 50 million pairs. Here's the trick. Put one finger
on the cheapest item and one on the most expensive. Add them. If the total is too big, move the right finger one step left
to a cheaper item. If it's too small, move the left finger one step right to a pricier item. Stop when they match or
when the fingers meet. Let's trace it. 5 + 45 is 50, which is too big. So, the right finger moves to 32. 5 + 32 is 37,
which is too small. So, the left finger moves to 12. 12 + 32 is 44, too big. The right finger moves to 25. 12 + 25 is 37.
Too small. The left finger moves to 18. 18 + 25 is 43. That's a match. Now try one yourself. Same prices, but
the card is worth $30. Which two items? Pause and work it out. 5 + 45 is too big. 5 + 32 is still too big. 5 + 25 is
30. That's your pair. Why does it work? Because the list is sorted. Every step rules out one item for the rest of the
search. The fingers only move toward each other. So the whole search is one pass. That's O of N instead of O of N
squared. Now the sliding window. Say the store wants its best 3-day sales stretch. The daily sales are 4 2 7 1 5
and 3. The obvious way is to add up every group of 3 days from scratch. For long periods, that's a lot of repeated
adding because neighboring groups share most of their days. Here's the trick. Add up the first three days once. 4 + 2
+ 7 is 13. Now slide the window forward one day. The newest day joins and the oldest day drops out. So you add the new
day and subtract the old one. The next total is 13 + 1 - 4. That's 10. Slide again. What's the next total? Pause and
work it out. It's 10 + 5 - 2. That's 13. One more slide gives 13 + 3 - 7 which is 9. The best stretch is 13. Each slide
takes just two steps, however wide the window is. So the whole job is one pass O of N. Both tricks win the same way.
They never redo work they've already done. Use two pointers when you're looking for a pair in sorted data. Use
the sliding window when you're looking at stretches of things in a row. Those could be days, readings, or letters in a
word. You've now met four structures. They're arrays, linked lists, stacks, and cues. The hard part isn't learning
them. It's choosing between them in real code. Say you're reviewing a pull request. That's a code change a teammate
sends you to check before it's added to the main code. They replaced a plain list with a linked list. Their note
says, "Inserts are O of one." But the code mostly reads items by position and adds to the end. Is it a good change? It
comes down to one habit. Ask what operations the code really does and how often. Does it look items up by position
or add at the end? What about inserting in the middle? And does it want the newest item first or the oldest? If the
code does looks by position, appends at the end, and scans in order, use an array. It does all three cheaply. Now,
say the code inserts and removes a lot at the front or next to nodes it already holds, and it rarely looks up by
position. Then a linked list may fit, but measure before switching. Back to that pull request, the code reads by
position and adds to the end. That's the array's job. So, you'd ask your teammate to keep the plain list. One distinction
matters here. Arrays and linked lists are ways to lay data out in memory. Stacks and Q's are rules about which
item comes out next. So you can build a stack or a que on either one. Want the newest item first? That's a stack.
Oldest first, that's a que. Need both ends? That's a deck. Let's try one. A support app keeps the last 50 customer
messages on screen. New messages arrive at the end. The oldest ones drop off the front and the screen shows them in
order. The operations are add at the back, remove from the front, and walk in order. That's a Q. A circular array, the
ring of seats, does all three cheaply. Here's another one. Take a moment to choose before I do. A background email
system sends jobs in the order they arrive. Once in a while, a customer cancels. Then the system gets a job ID
to remove. The main operation is oldest first, so it's a queue. New jobs join the back and the sender takes from the
front. The cancel is different. It's a lookup by value. You walk the queue and check each ID. That's O of N. Is that a
problem? Cancels are rare. Maybe a few a day against thousands of sends. Scanning a few thousand jobs now and then costs
almost nothing. So, keep the queue and accept the scan. If cancels get frequent, you could add a hashmap.
That's the lookup table you met earlier and it finds each job by its ID. Keep the queue as a doubly linked list. Then
the map finds the job and the list unlinks its node quickly. Real features often do this. One structure rarely does
every job. So two often work together. Notice one thing all four lack. None of them can find an item by its value
quickly. Asking is this customer here? means checking each item and that's O of N. A sorted array can use binary search
the having trick but then every insert pays to keep it sorted. That single gap is why hashmaps and trees exist. That
covers the simplest ways to hold a collection. A data structure is a way of arranging data so that some jobs are
fast. No arrangement is fast at everything. An array keeps items side by side. So reading any position takes one
step and walking in order is quick. Adding at the end is cheap on average, but inserting in the middle means
shifting everything after it. A linked list chains items with pointers. Changing it next to a node you hold is
cheap. But reaching a position means following the chain, so the array usually still wins. And two everyday
tricks, two pointers and the sliding window turn many quadratic array jobs into a single pass. A stack serves the
newest item first for undo, brackets, and the call stack. A Q serves the oldest first for fairness and for
working through a rush in order. Build a Q on a ring of seats or a linked list. Never by removing from the front of a
plain array. So when you pick a structure, ask one thing first. What does the code really do with it? And how
often? None of these four can find an item by its value quickly. The structures in the next module fix that.
The last module ended with a gap. None of those structures can find an item by its value quickly. That gap matters
because some questions come up in almost every app. What's the most urgent ticket right now? What's the cheapest way
across town? Which row out of 10 million matches this email? The structures ahead answer questions like those fast. You'll
meet hashmaps, trees, heaps, and graphs, and see how to walk a graph. After that comes how real systems combine them in a
cache and in a database index. And at the end you'll see where all of them show up in one real app. That's where
both of the courses questions matter most. How does it grow? Where does it live? Let's start with the most common
question of all. The most common question in code is simply this. Have I seen this before? Here's a mistake that
shows up in customer imports all the time. Before saving each customer, the code checks whether that email is
already in a list of every email seen so far. With a few hundred customers, it's instant. With 200,000, the import
freezes. Nothing in the code looks slow. Someone just used a list where a set belonged. You've already seen why a list
hurts here. Each check walks the whole list. So, the import is a loop inside a loop. Every structure in the last module
has the same gap. To find an item by its value, it checks item after item. The fix is a hashmap. To see the idea,
picture a filing cabinet with 26 drawers, one for each letter of the alphabet. To file a customer's card, you
look at the first letter of their name. Sarah's card goes in the S drawer. Later, to find Sarah, you look at the
first letter again and go straight to the S drawer. you never search the other 25. A hashmap works the same way with a
smarter rule than the first letter. Say you want to store a customer's email. First, a hash function turns the email
into a number. That's all a hash function does. It turns any input into a number. And the same input always gives
the same number. Then the map divides that number by how many slots it has and keeps the remainder. The remainder is
the slot like the drawer. Try it. Say an email hashes to 27 and the map has eight slots. Which slot does it go in? Pause
and work it out. 27 / 8 is 3 with three left over. So it goes in slot three. Later to check for that email, you hash
it again. You get 27 again and slot three again. You go straight there with no scanning. That's why adding, finding,
and removing in a hashmap all take about one step on average. And that's why hashmaps are everywhere. The
dictionaries and lookup tables in your language are usually hashmaps underneath. Back to the frozen import.
Checking a list was a loop inside a loop, so the import was quadratic. With a hashmap, each check takes about one
step, so the whole import is linear. 200,000 customers take about 200,000 steps, not 20 billion. You've already
met its partner, the hash said. It's the same structure, but it stores only keys with no values attached. It's the
fastest way to answer, "Have I seen this before?" Which is exactly what the import was asking. One thing a hashmap
doesn't give you is order. The slots come from remainders, so the items end up scattered. For the import, that
didn't matter. It only needed to know what it had already seen. So, here's what to take away. When code keeps
asking, "Have I seen this?" Use a hash set or a hashmap, not a list. A hashmap jumps straight to a slot. So, finding a
key takes about one step on average, but that average depends on a few things going right. Here's what happens inside.
Start with a problem. Two different keys can land in the same slot. That's called a collision, and it can't be avoided.
There are far more possible keys than slots, so some must share. Think back to the filing cabinet. Lots of names start
with S, so the S drawer holds many cards. A hashmap has the same problem, just less often. There are two common
fixes. One is chaining. Each slot keeps a short list, and keys that collide simply join that list. The other is
called probing. If the slot is taken, try the next one and keep going until you find a free one. Either way, as long
as collisions stay rare, lookups stay close to one step. Let's watch it on a tiny map with eight slots. Anna's email
lands in slot three. Ben's lands in slot six. Cara's also lands in slot three, so it collides with Anna's. With chaining,
Cara's joins a short list at slot three behind Anna's. Devs lands in slot one. Collisions get common when the map gets
too full. So, the map keeps track of how full it is. Four items in eight slots means it's half full. Say this map grows
when it passes half full. Then a fifth email, EES, arrives and takes it past half. Before I go on, guess what has to
happen to the emails already stored? Everyone has to move. The map sets up 16 slots and works out each slot again. Now
dividing by 16, the hash numbers don't change, but the remainders do. Anna's might move to slot 11, while Cara's
stays at three. Now they're no longer sharing. Moving everything costs O of N, but it happens rarely. Just like a
growable list, that cost gets spread out. So adding still takes about one step on average. That move also shuffles
the order of the items. So never rely on the order a hashmap gives you back unless your language promises one. Two
more rules keep a hashmap healthy. First, a key must never change while it's stored. If it does, its hash
changes, the map looks in the wrong slot, and the item is lost. That's why many languages only let you use keys
that can't change, like strings and numbers. Second, the hash function has to spread keys evenly. If many keys
crowd into a few slots, lookups get closer and closer to O of N. Attackers can even send keys designed to collide.
The hash functions built into your language are designed with that in mind. So don't write your own. So when a
hashmap feels slow, check the basics. Are the keys changing? Is the hash function a good one? And is anything
forcing collisions? Bast lookup isn't always enough. Some features also need things kept in order all the time. Say
you're building a game leaderboard. You need to look up any score quickly and show the scores in sorted order. A
hashmap handles the lookup. But a hashmap knows nothing about order. Ask it for the smallest score and it has to
check every entry. So what gives you fast lookup and sorted order together? That's what a binary search tree is for.
Remember the nodes from linked lists, each pointing to the next? Let a node point to more than one node below it and
you get a tree. A tree has no loops. One node is the root. Each node has children and a node with no children is a leaf.
Anything with levels is a tree like folders inside folders or a chart of who reports to whom at a company. Any node
with everything below it is called a subtree. Recursion is the natural way to walk a tree because each subree is
itself a tree. In a binary search tree, binary means each node has at most two children, a left and a right. Search
tree means there's one order rule. Everything in a node's left subree is smaller. Everything in its right subree
is larger. That rule builds binary search, the having trick, right into the structure. To find a value, start at the
root. If it's smaller, go left. If it's larger, go right. It's like a number guessing game where every higher or
lower rules out a whole side. Each step throws away a whole sub tree. If the tree is balanced, its height grows only
with log N. Each comparison takes you one level down. That gives you O of log N to find, insert, or delete. Keep that
word balanced in mind. A plain binary search tree doesn't promise it. Let's follow one tree. Insert 50, 30, 70, 20,
40, 60, and 80 in that order. 50 becomes the root. 30 is smaller, so it goes left. 70 is larger, so it goes right. 20
is smaller than 50 and smaller than 30, so it sits left of 30. 40 is smaller than 50, but larger than 30, so it sits
right of 30. In the same way, 60 lands left of 70 and 80 lands right of 70. That's seven values in three levels,
perfectly balanced. Now search for 60. Start at 50. 60 is larger, so go right to 70. The whole left side is gone. 60
is smaller than 70, so go left. There's 60. That's three checks out of seven values. Now, where does the sorted list
come from? It comes from a walk called a traversal. A traversal visits every node once. The in order traversal visits the
left subree, then the node, then the right subree. Before I trace it, what's your guess for the order? Pause and
think. It visits 20, 30, 40, 50, 60, 70, 80. It's sorted every time because everything smaller sits to the left. And
because the tree keeps everything sorted, it can answer more than lookups. It can find the smallest value, the next
value after this one, or everything in a range. That's the case for a search tree. It gives you order and fast lookup
together. A binary search tree is fast when it's balanced. Each step down throws away a whole side. So finding a
value takes about login steps, but nothing in the treere's rule keeps it balanced. Let's break it on purpose.
Insert 10, 20, 30, and 40 in that order into an empty tree. 10 becomes the root. 20 is bigger, so it goes right. 30 is
bigger than both, so it goes right of 20. And 40 goes right of 30. Pause and picture it. What shape is that tree?
It's a straight line leaning right. Four values take four levels, and finding 40 means checking every one. It's really
just a linked list. So lookups are O of N. Feed a plain tree sorted data like dates or ID numbers that only go up and
this is what you get. Self-balancing trees fix this. Every time you insert or delete, they check whether one side has
grown too deep. If it has, they do a small reshuffle called a rotation. Here's one rotation on the same example.
When 30 arrives, the right side is two levels deeper than the left. So the tree rotates. 20 moves up to the root with 10
on its left and 30 on its right. When 40 arrives, it goes to the right of 30. Now four values take three levels instead of
four. Keep inserting sorted values and the rotations keep going. After a million sorted inserts, the tree is
somewhere between 20 and 40 levels deep, not a million. A plain binary search tree hopes for balance. A selfbalancing
tree makes sure of it. You won't write rotations yourself. Java's tree map and C's sorted dictionary are self-balancing
trees and you just use them. Python and JavaScript don't have one built in, so you'd use a library. You may hear the
names red black tree and AVL tree. Those are two popular ways of doing the balancing. Databases use a related tree
called a B tree. Each node holds many values and has many children, so the tree stays very short. That matters when
every step means a read from disk. So, when do you want a tree instead of a hashmap? Back to the game leaderboard. A
hashmap finds a player's score in about one step, but it has no idea of order. A balanced tree takes about login steps,
but it keeps everything sorted. In practice, a hashmap lookup usually lands in one slot. A tree lookup follows 20 to
40 links through scattered memory. So, when you only need lookup, the hashmap usually wins. When you need order, too,
the tree is worth it. So, next time, ask one question. Do I need order or just look up? Sometimes you don't need
everything in order. You just need the most urgent item right now. Think about a hospital emergency room. Patients
aren't seen in the order they arrived. Someone with a sprained ankle waits while someone having a heart attack goes
straight in. Whoever is most urgent goes next. Software needs the same thing. On Monday morning, a support system fills
up with weekend tickets, mostly routine password resets. Then a ticket arrives saying the whole site is down. The next
free agent must get that one first. Each ticket has a priority number, and number one is the most urgent. A plain Q won't
do because it serves whoever waited longest. Sorting the whole backlog after every new ticket works, but it gets
slower as the backlog grows. What you need is a priority queue. You heard that name in the lecture on cues. It always
serves the most important item, whatever order things arrived in. The structure that makes it fast is called a heap. A
heap is a tree with one simple rule. No parent is bigger than its children. It doesn't keep everything sorted the way a
search tree does, but because of that one rule, the smallest item always sits at the top. So, what's most urgent takes
one step. You just look at the top. Adding an item is like a new patient arriving. They start at the back, then
move ahead of anyone less urgent. In a heap, the new item goes into the next free spot at the bottom. Then it swaps
with its parent again and again as long as the parent is bigger. Let's try it. The heap's top is two. Below it are five
and three. Below the five are nine and seven. Now a new ticket with priority one arrives. It goes into the next free
spot under the three. One is smaller than three, so they swap. Now one sits under the two. Where does one end up?
Take a second. One is smaller than two, so they swap again. It ends up at the top where the most urgent item belongs.
Taking the top item out works the other way around. Remove the top. Move the last item up into the empty spot and let
it sink. It swaps with its smaller child until the rule holds again. Each swap moves one level. A heap is filled level
by level with no gaps. So it's always about login levels deep. That means adding and removing both take about
login steps. And because there are no gaps, a heap fits into a plane array with no pointers at all. That makes it
fast in practice, too. Flip the rule. So no parent is smaller than its children and the biggest item sits on top. That's
called a max heap. Which one you use just depends on whether small or big numbers mean most important. Heaps show
up wherever you need the next most important thing. They schedule jobs by deadline. They find the top 10 of a
million items without sorting them all. And in route finding, they pick the closest unexplored point next. There's
one more thing to know. A heap doesn't remember arrival order among equal priorities. So two priority two tickets
can come out in either order. If first come first served matters within a priority, add the arrival time as a
tiebreaker. So a hashmap finds by key and a search tree finds by key in order. A heap finds the most extreme item.
Lists and trees handle a lot, but they can't model friendships. A list can hold the people and a tree can hold a
hierarchy. But friendships have no top and no single parent and they loop back. Your friend's friend may already be your
friend. Take the people you may know feature in a social app. It needs your friends and their friends. That calls
for a structure where anything can connect to anything. Start with a tree and remove its rules. Let a node point
to any number of other nodes. allow loops and drop the root. That's a graph. It's one of the most general structures
there is because so much of the real world is things connected to things. The vocabulary is small. The things are
called vertices or nodes. The connections are called edges. Anywhere you can say this is connected to that,
you have a graph. Road maps, social networks, and the internet all work this way. Edges have two properties. They can
be directed or undirected. A friendship goes both ways. A follows relationship or a one-way street goes one way. And
edges can be weighted or unweed. A road has a length and a flight has a price. A friendship usually has no number.
Directed and weighted edges are what let graphs model routing problems. There are two common ways to store a graph. An
adjacency list gives each vertex a list of the vertices it connects to. It's compact when most vertices connect to
only a few others. Most real graphs are like that. And walking a vertex's neighbors is a short scan. An adjacency
matrix is a grid with a row and a column for each vertex. There's a mark wherever an edge exists. Checking for an edge
between two vertices is O of one. But the grid has n squared cells. For a million vertices, that's a trillion
cells. So, it only suits small graphs or graphs where most points connect to most others. Here's a small graph you'll use
for the next few lectures. Picture six intersections A through F joined by seven two-way roads. A connects to B and
C. B connects to D and C connects to E. D and E connect to each other and both connect to F. As an adjacy list, A's
entry reads B C. D's entry reads B E F. F's entry reads D E. Each road shows up twice, once in the list at each end. Now
try one yourself. A matrix for this map needs a row and a column for each intersection. How many cells is that?
And how many hold a mark? Pause and work it out. It's 6x6, so 36 cells. Each of the seven roads marks two cells, one for
each direction. So only 14 are marked and most of the grid is empty space. That's why adjacency lists usually win.
Graph questions come in many forms. Is there a path from here to there? What's the shortest one? What's reachable from
this point? Are there cycles? Who's two connections away from you? That's our people you may know. Each of these is a
walk over the graph. The walk visits vertices and follows edges. it must remember where it's been. Unlike a tree,
a graph has loops and you can circle forever. Graph traversal is about that memory and about the order of the
visits. It's where the stack and the que come back. A list knows what comes next. A tree knows what sits above. A graph
knows what's connected. To answer any of those graph questions, you have to walk the graph. There are two basic ways to
do it, and they differ by one data structure. This one uses a Q, the same first in first outline from the last
module. Take the six intersections from before. As a reminder, A connects to B and C. B connects to D and C connects to
E. D and E connect to each other, and both connect to F. When a point has several neighbors, take them in
alphabetical order. The question is, how do you get from A to F with the fewest roads? Every walk like this follows the
same steps. They keep a collection of vertices to visit next. They also keep a hash set of vertices already seen. That
scene set is what stops the circling. You never process a vertex twice and you never loop forever. Then take a vertex
from the collection and look at its neighbors. Mark any unseen ones as seen and add them to the collection. Repeat
until the collection is empty. Every reachable vertex is processed once. Each two-way road shows up in the lists of
both its intersections. So it gets looked at twice at most. That's still O of vertices plus edges. The work grows
with the size of the graph. Make it a Q and you get bread first search or BFS. A Q is first in first out. You visit the
start, then all its neighbors, then all their neighbors. The walk expands outward in rings. Start BFS at A. Mark
it seen and the Q holds just A. Take A out. Its neighbors B and C are new. So the Q becomes B C. Take B. What goes
into the Q now? Take a second. B's only new neighbor is D. So the Q is C D. Take C. That adds E. So the Q is D E. Take D.
Its neighbor E is already seen but F is new. Now the Q is E F. Take E. Everything around it is already seen. So
the Q is just F. Take F and the Q is empty. The visit order is A B C D E F. Now look at the rings. A is distance
zero. B and C are distance 1. D and E are distance 2 and F is distance 3. F was discovered from D and D was
discovered from B. So the fewest hops path is A B D F. That's three roads. BFS reaches each vertex by the fewest
possible edges. So, it finds shortest paths when every edge counts the same. That makes BFS the walk for questions
like these. How many introductions separate these two people? What's the fewest moves to solve this puzzle?
What's within two hops of this node? Real roads aren't equal, though. Some are longer, some are slower, and some
cost money to use. On a map like that, the fewest hops isn't always the cheapest route. Breath first search used
a Q, so the walk spread out in rings. Now make one change. Swap the Q for a stack and you get depth first search or
DFS. Use the same six intersections and the same alphabetical rule. You visit the start, then one neighbor, then one
of that neighbors neighbors. You go as deep as possible, then back up to try another branch. If you write DFS
recursively, the call stack is the stack. That's why DFS is often just a recursive function. The walk I'm about
to trace follows the recursive version. A handwritten stack goes deep the same way, but it may pick branches in a
different order. Run DFS on those six intersections starting at A. Will it reach F by the shortest route? Make a
guess before I trace it. From A, go to B. B's first unseen neighbor is D, so go there. D's first unseen neighbor is E,
so go there. E's first unseen neighbor is C. Both of C's neighbors are already seen, so back up to E. E still has F
unseen, so go to F. The visit order is A, B, D, E, C, F. Now look at how DFS reached F. It went A B D E F. That's
four roads. But a bf would have taken only three for can I get to f at all? That's perfectly fine. For what's the
shortest way to F? It's the wrong tool. DFS takes the first branch it finds, not the shortest one. A simple way to
remember the difference is this. A Q spreads out. A stack goes deep. So what is DFS good for? It tells you whether a
path exists at all. It detects cycles and it explores every reachable branch of a maze. Searching every move in a
game uses the same idea with extra tricks to skip moves that can't win. DFS also puts tasks in order when they
depend on each other so that everything a task needs is finished first. That's called a topological order. It only
works when there's no loop in the dependencies. If A needs B and B needs A, no order works. So the tools that
build software projects use the same walk to spot that loop and report it. There's one more question. What does
each walk cost in memory? BFS can use a lot. Its Q may hold a whole ring of a wide graph at once. DFS keeps a stack
that grows with the depth instead. If it's written recursively, that's call stack depth, and a deep enough graph
overflows it. Use an explicit stack for deep graphs. So, here's the summary. A Q gives you
shortest paths by hop count. A stack gives you reachability, cycle detection, and dependency order. It's the same
steps with one structure swapped. Your map app finds the fastest route across a city in under a second. The city can
have a 100,000 intersections. The app doesn't try every route because there are far more routes than any computer
could check. Instead, it combines three things. There's a weighted graph, a priority Q, and a walk that expands
outward. The method is called Dystra's algorithm, named after the computer scientist who invented it. It makes one
assumption up front. No road can have a negative cost. You're at the start, and it costs zero to be there. Look at every
road out of the start and note the cost of reaching each neighbor. Then pick the unvisited intersection with the smallest
known cost so far and expand from there. for each of its neighbors. Check if going through this intersection is
cheaper than anything found before. If so, update that neighbor's best cost. Mark the intersection done. Then repeat.
Always expand the cheapest known unvisited point. Make it concrete with three intersections. You start at A. A
road from A to B costs five. A road from A to C costs two. And a road from C to B costs one. From A, you note B at five
and C at 2. Before you go on, guess is the direct road to B the best way there? The cheapest unvisited point is C, so
you expand it first. Going through C, B costs three. That's better than five. So B's best cost becomes three. Now B is
the cheapest unvisited point. You expand it and you're done. The route is A to C to B. The direct road looked shorter,
but the rule found the better route without trying every path. Why can you trust it? Think about the cheapest
unvisited point. Any other way to reach it would have to pass through some other unvisited point first. But every other
unvisited point already costs at least as much. And no road costs less than zero. So no detour can ever be cheaper.
Once a point is the cheapest, its cost is final. And when the destination becomes the cheapest point, its cost is
the answer. So you can stop. Picking the cheapest unvisited point each time is exactly what a heap is for. It hands it
over in about log end steps. Without a heap, every round would scan every point and the search would be quadratic. With
one, even a whole city takes well under a second. When costs differ from road to road, counting hops isn't enough. The
rule that works is to expand the cheapest known point. Here's that rule at work on a bigger map round by round
so you can watch the priority queue do its job. Take the same six intersections and now give each road a cost. A to B
costs four and A to C costs one. B to D costs two, C to E costs two, and D to E costs two. D to F costs 1 and E to F
costs five. We want the cheapest route from A to F. Round one. Expand A at cost zero. B gets four and C gets one. The
priority Q holds C at 1 and B at four. Round two. C is cheapest at 1. Through C. E costs three. The Q now holds E at
three and B at four. Round three. E is cheapest at three. Through E. D costs five and F costs 8. The Q holds B at
four, D at 5, and F at 8. Round four. B is cheapest at four. Through B, D would cost six. That's worse than five, so
nothing changes. Expanding a point doesn't always improve anything. The Q still holds D at 5 and F at 8. Round
five. D is cheapest at five. Through D, F costs six. That's better than eight. So F's best cost drops to six. The Q
holds just F at six. Round six. F is the cheapest unvisited point at six. It's the destination, so we stop. Follow the
improvements backward and the route is A C E D F. The total cost is six. What would plane BFS pick on this map? Take a
second. BFS ignores costs and counts roads. Its answer is A, B, D, F. That's only three
roads. But those roads cost 4, 2, and 1. That adds up to seven. Dystra's route uses four roads and costs six. Fewest
hops isn't the same as cheapest. BFS is this same walk with every edge costing one. In that case, a plane Q gives
cheapest first order automatically. Weighted edges break that and the priority Q restores it. There are
limits. The algorithm assumes costs aren't negative. A negative cost edge breaks the nothing cheaper can appear
later guarantee. Then you need a different algorithm. Map apps also use an idea called AAR. They add a guess of
the remaining distance to steer the search toward the destination. And fastest versus shortest versus cheapest
depends entirely on which numbers you put on the edges. So remember this, fewest roads and cheapest route are
different questions. A plane Q answers the first. A priority Q answers the second. So far, each structure has
worked on its own. Real systems rarely use one alone. Often the best answer is two simple structures working together.
Every profile view in your web app sends a request to the database. So you decide to keep the thousand most recently
viewed profiles in memory. When that space fills up, you throw out the one nobody has looked at for the longest
time. That's an LRU cache, short for least recently used. It has three jobs. First, look up a profile by customer ID,
fast. Second, every time a profile is read, mark it as the most recent. Third, when the cash is full, find the least
recent entry and remove it. Throwing an entry out like that is called eviction, and it has to be fast, too. These happen
on nearly every request, so fast here means O of one. Try the obvious structure first. A hashmap gives you
lookup by ID in about one step. But a hashmap has no sense of order. To find the least recently used entry, you'd
scan every entry and compare timestamps. That's O of N, a thousand checks on every eviction. So try a list instead.
Keep it in order with the most recent at the front and the least recent at the back. Now eviction is easy. You drop the
item at the back. But to look up by ID, you walk the list until you find it. That's O of N. And marking an item as
most recent means moving it to the front. You have to find it first. Each structure is good at exactly what the
other is bad at. The fix is simple. Don't choose, use both. Keep a doubly linked list where each node points both
ways, like the one from the last module. Order it from most recent at the front to least recent at the back. Then keep a
hashmap from customer ID to that customer's node in the list. The map doesn't point to the profile directly.
It points to the node and the node holds the customer ID and the profile. Eviction needs that ID to clean up the
map. Now every operation is short. To read a customer, ask the hashmap for their node. That's O of one on average.
Unlink that node from wherever it sits and attach it at the front. That's just a few pointer changes. To evict, take
the node at the back, remove its ID from the hashmap, and unlink it. To add a new customer, create a node at the front,
and put its ID in the map. No step ever walks the list. Let's watch it with a cache that holds only three. Customer A
is viewed, so the list is just A. Then B is viewed and goes to the front, so the list reads B A. Then C arrives and the
list reads C B A. Now A is viewed again. The hashmap hands us A's node at the back. We move it to the front. The list
now reads A C B. Now customer D is viewed and the cash is full. Take a second and guess which one gets thrown
out. It's B. Many people guess A since it came in first. That's not a silly guess. It's exactly how a Q would
decide, oldest first. But A was just used, so it moved to the front. B sits at the back, untouched since it arrived.
We unlink B, delete B's entry from the map, and put D at the front. The list reads D A C. Each structure covers what
the other is bad at. That cache pairs a hashmap with a doubly linked list. Why does the list need pointers going both
ways? Work through it by hand. Say the list reads A CB from most recent to least recent. Customer C is viewed again
and the hashmap hands you C's node. To move C to the front, you first have to take it out of the list. That means
making A point past C straight to B. Here's the question. In a list where each node only points forward, how do
you find A, the node just before C? Take a second. You can't, not directly. C only knows what comes after it. So,
you'd walk from the front of the list until you reach the node that points to C. That's O of N, the very cost the cash
was built to avoid. Now, give every node a back point or two. C already knows that A is behind it and B is ahead of
it. So you point A at B, point B back at A, and move C to the front. That's a few pointer changes with no walk at all. So
it's O of one. Throwing out the oldest entry works the same way. The node at the back already knows which node
becomes the new back. Combining two structures has a cost, though. You now have two structures that must always
match. Update the map, but not the list, and you get bugs that are very hard to track down. Each entry also carries
extra memory. That's a map slot plus two pointers on top of the data. Many languages come with an ordered map or a
readymade LRU helper. Use that rather than writing your own. Building one by hand is mostly a classic interview
question. It's a good one because it tests whether you understand why each piece is there. Here's one last warning.
The size limit isn't a detail. A cache that never throws anything out behaves like a memory leak. That's memory a
program keeps holding and never gives back. The cache keeps growing until the server runs out of memory and crashes.
So build the cache from a hashmap and a doubly linked list. Keep the two matching and always set a size limit.
Cache keeps a little of your mostused data in memory. Most of your data lives somewhere much bigger and slower. It
lives in a database on disk. A slow login page is one of the most common performance complaints I've dealt with.
The page looks up a customer by email. In testing with a small table, it's instant. In the live app with 10 million
customers, the same request takes seconds. A request like that to a database is called a query. The
difference is in how the database finds the row. Without help, the database has one option. It reads every row in the
table and checks each email. That's called a full table scan and it's O of N. Worse, the rows live on disk or in
pages loaded from disk. Disk is far slower than memory, so every extra read costs real time. That's a lot of pages
to pull in for one customer. The fix is an index. An index is a separate structure that tells the database where
each row lives. It's usually kept sorted by a column's value. It works like the index at the back of a book. You look up
a word in the sorted list and it gives you a page number. So what shape is it? You might guess a binary search tree
sorted with login lookups. But there's a problem. A database reads from disk in fixed-sized chunks called pages or
blocks. A binary tree node holds one key and two children. Walking down means one expensive page read for every level. For
10 million rows, that's about 24 levels and possibly as many page reads. The answer is to make each node one full
page. A page can hold hundreds of keys and hundreds of child pointers. That's the B tree you heard about with balanced
trees. Every node is wide instead of tall. Most databases use a close variant called the B+ tree, but the idea is the
same. One page read now narrows the search by a factor of hundreds, not two. Let's put rough numbers on it. Say each
page holds about 500 keys. How many page reads would it take to find one customer among 10 million? Take a guess. The root
page points to 500 pages below it. Those pages point to 500 * 500 pages. That's 250,000
pages. Each of those bottom pages holds 500 entries. That means the third level covers 125 million rows. So in this
rough model, finding one customer among 10 million takes about three page reads. Add a fourth level and you're past a
billion. The top levels are read constantly, so they usually stay in memory. Often only the last read or two
really touches disk. Some databases keep the rows themselves in that bottom level. The lookup still works the same
way. Because a B tree is sorted, it does more than exact lookups. Take a query like customers who signed up last week.
It finds the first matching date. Then it walks forward through neighboring entries until the dates run out. A query
that sorts by signup date can read the index in order. It doesn't need to sort the rows. Some databases also offer a
hash index. It works like a hash map. One hash takes you straight to the entry. It's great for exact matches like
one email. It can't answer ranges or sorting because hashing scatters the order. So when a lookup is slow on a big
table, the first question is whether an index can find the row. So an index makes finding rows fast. Using indexes
well takes a few rules. Indexes aren't free. Each one takes disk space. Every insert, update, or delete also has to
maintain the indexes it affects. The database batches some of that work, but more indexes still mean more work on
every right. So, writes get slower, and indexing every column is a mistake. Here's the main rule. Index the columns
you search by and sort by and not much else. An index helps most when a query picks out a small slice of the table.
Try this one. A query asks for every customer whose account is active, and n out of 10 of them are. Will an index on
that column help? Take a second. Probably not. Walking the index and then fetching nine rows out of 10 is slower
than just reading the whole table once. So, a good database will skip the index. Also, watch out when your query wraps a
column in a function. For example, it might lowercase the email before comparing. The index holds the original
values, so it often can't help. The same goes for a search for every email that ends with gmail.com.
A sorted list can't help when you don't know how the value begins. Now, here's the case that confuses many people. It's
an index on two columns called a composite index. Picture an index on last name, then first name, like a class
list sorted by last name. Which of these three queries can use it? One finds everyone with the last name Garcia. Two
finds Anna Garcia by last name and first name. Three finds everyone named Anna with any last name. The first two can
usually use it. The list is sorted by last name, so all the GarcA sit together within them. Anna is easy to find. The
third can't use it the normal way. Every Anna is scattered across the whole list, one under each last name. Some databases
can still scan the entire index, but that's no shortcut. Column order in a composite index matters. Finally, don't
guess. Every major database has an explain or query plan feature. It shows whether a query uses your index or falls
back to a full scan. I've seen one missing index once added take a query from seconds to milliseconds. That check
is how you'll spot it. There are a lot of structures to choose from like hashmaps, trees, heaps, and graphs. Each
one is built for a different job. The real skill is picking the right one. Picture a design review. That's a
meeting where the team checks a plan before it's built. Someone asks, "What structure holds this data and why?" A
list because that's what we use. Isn't an answer. Neither is a hashmap because they're fast. A good answer starts from
the work. Name the question your code asks most often. Then match it to the structure built for that question. Let's
practice. I'll give you a question your code might ask. Pick the structure before I do. First question, is this
coupon code valid? Take a second. That's a hash set. It answers, is this here in about one step. Next, give me the
customer at position 40 on this page. That's an array. Jumping to a position takes one step. Next, show every product
priced between 20 and $50, cheapest first. Think about it. You need lookup and order together. That's a balanced
search tree. It can jump to $20, then walk forward in order until it passes 50. Next, which delivery is most urgent
right now? That's a heap. It always keeps the most urgent item on top. Next, undo the last change. That's a stack,
newest first. And print these documents in the order they were sent is a Q, oldest first. Add and remove right next
to items I'm already holding is the rarer case for a linked list. Last one. Is there any road route from the
warehouse to this town? That's a graph. You walk it from the warehouse and see whether you reach the town. Notice what
you were doing. You never started from the structure. You started from the question and the question pointed to the
structure. There are three traps to watch for. The first is picking by habit instead of by the question. A list used
for is this here checks every item. And that's the quadratic loop again. The second is forgetting about small sizes.
For a handful of items, a small array checked in order can beat a hashmap. The cache makes that scan very fast. The
third is building your own. The structures built into your language are already good versions. Use them and know
what each one costs. Knowing what each structure is good at is one thing. Picking one in a real design review is
another. So, let's practice the habit from before. Start from the work, not the structure. Let's work one through
the way you would in a review. You have 50,000 customer records. The app looks customers up by email all day. Records
get updated regularly. And the admin screen lists customers sorted by signup date, one page at a time. Pause and pick
before I do. Start with the most frequent operation. Look up by email. A hashmap keyed by email makes that about
one check instead of up to 50,000. That's the main structure. But a hashmap has no order, so it can't serve the
sorted admin screen. You could sort all 50,000 every time the screen loads. That's n login per page view. Or you
could keep a second structure, a balanced tree keyed by signup date with the customer ID to break ties. That
gives you the sorted walk directly. Two structures means more memory and every insert or delete must update both so
they always match. If the admin screen opens twice a day, sorting on demand is simpler and fine. If it opens
constantly, the tree is worth it. The answer comes from how the app is really used, not from the table alone. Here's
another. So, take a moment and decide. A support queue must always serve the highest priority ticket next. New
tickets arrive all day. That's a heap used as a priority queue with the most urgent ticket on top. Inserting each new
ticket is O of login. Taking the most urgent is O of login 2. Why not keep a list and sort it each time? Sorting is n
login and you'd repeat it on every arrival. Why not a hashmap? It finds a ticket by ID instantly, but it can't say
which ticket is most urgent without scanning them all. If agents also look tickets up by ID, add a hashmap beside
the heap. As before, both must always match. One more and guess first. A social app suggests people you may know.
These are people two connections away who aren't already your friends. The question is what's connected to what? So
it's a graph. Each person is a vertex and each friendship is an edge. Adjacency lists hold each person's
friends. An adjacy matrix would be almost all empty. Each person knows only a tiny share of everyone. Run breath
first search from you and stop at depth two. Level one is your friends. Level two is their friends and those are the
candidates. Keep a hash set of you and your friends. For each person you reach at level two, check that set first so
you never suggest yourself or someone you already know. Then add one to that person's count in a hashmap. The same
person turns up through many mutual friends. So the count tells you how many you share. Each person still appears
once in the suggestions ranked by that count. The two question test ties it together. How does it grow? That's the
big O column. Where does it live? That's whether the data sits side by side in memory, which the cache likes, or is
scattered and linked by pointers. Answer both and you'll rarely pick wrong. You know the main data structures now, but
most developers are left with one question. Where in a real product do you really get to choose one? Start with a
surprise. In a lot of everyday code, you don't. When your app saves an order or looks up a customer, the database does
the work using structures it picked for you. So where do your choices really happen? Mostly in four places. There's
code that works on data already in memory. There are caches that keep popular data close. There are cues that
pass work between parts of the system. And there's choosing which database indexes to add. Let's walk through an
online store and find those choices one feature at a time. For each one, guess the structure before I answer. First,
the recently viewed strip. It shows the last 10 products a shopper looked at. Newest first. View a product again, and
it jumps to the front. When the strip is full, the oldest one drops off. Take a guess. This one needs two jobs at once.
It has to find a product fast to see if it's already in the strip, and it has to move or drop items at the ends quickly.
No single structure does both, so you pair two. A hashmap finds the product in one step. A doubly linked list keeps the
order. So moving a product to the front or dropping the oldest takes one step, too. That pair is called an LRU cache
for least recently used. Second, the top 10 best sellers box on the homepage. Sales keep coming in all day, and the
box always shows the 10 biggest sellers. What would you use? Sorting every product after every sale would be
wasteful because you only care about the top 10. A heap is built for this. It always knows its biggest item and adding
a new one takes about login steps. So you never have to sort the whole catalog. Third, the emails after
checkout, like a receipt and a shipping notice. On a sale day, thousands of orders land in a few minutes. Which
structure? It's a queue. Checkout adds each email job to the back and finishes right away. A worker sends them from the
front, oldest first. The queue holds the whole rush and nobody waits on a loading page. Fourth, the customers also bought
row. Picture every product as a point with a line between two products whenever people buy them together. What
is that? It's a graph searched one or two hops out, just like people you may know. In a big store, that search
usually runs ahead of time and the results are saved for quick lookup. One last feature is the order history page.
Sorted by date, 10 orders at a time. Here, the right answer is usually to let the database do it. An index on the
customer and the order date gives you sorted pages directly. Your job is to add the right index, not to build a tree
yourself. Notice the pattern. Real features often need two structures working together. And sometimes the best
choice is to let the database choose. So here's a checklist to use on any feature. First, list what the feature
does with its data. Second, find the job it does most often. Third, match that job to a structure. Fourth, ask how big
the data can get. And fifth, before you switch to something clever, measure that covers the structures behind the
questions every app asks. A hashmap turns a key into a slot. So, have I seen this? Takes about one step. It stays
fast as long as keys don't change and collisions stay rare. A search tree keeps things in order, but only a
self-balancing one stays fast on sorted data. A heap always knows the most urgent item. And a graph models anything
connected to anything. To walk a graph, a Q spreads out in rings and finds the fewest hops, while a stack goes deep.
When roads have different costs, Dystra always expands the cheapest point. Next, real systems combine structures like a
hashmap and a doubly linked list in an LRU cache. And a database index is a wide shallow tree. It turns a full scan
into a few page reads at the cost of slower writes. In a real product, many of your choices come down to caches,
cues, and which indexes to add. So when you choose a structure, start from what the code does most and how often. Next,
the last module looks at what happens while your code runs. Everything you've learned so far runs on a real machine.
It runs inside a runtime, the software that runs your code, and that's where some of the hardest bugs begin. A
service might be slow for its first few minutes. Memory might climb for days until someone restarts the server, or a
counter might come up short, but only when many people use the app at once. This module looks at what happens while
your code runs. It starts with how your code becomes instructions the processor can run. Then it covers how memory gets
cleaned up and why it still leaks. Next comes what goes wrong when several things run at the same time. And at the
end, everything in the course comes together on one slow endpoint that also gives wrong answers. So let's start with
how your code reaches the processor. Say you've just put a new version of a Java service live. The first requests are
slow. A few minutes later, the same requests are fast. You haven't changed a line of code. So what changed? Most
people first suspect the database or the network. Here the cause is the runtime itself. The answer is in how your code
gets turned into something the processor can run. The processor doesn't understand your code. It understands
machine instructions. These are number codes for small steps like add these compare those and jump there. Something
has to turn the text you wrote into those instructions. There are three basic ways to do it. The first way is to
compile. A program called a compiler reads all of your code first. It checks it, then turns it into machine
instructions ahead of time. The result runs directly on the processor with no translating while it runs. That's why
compiled programs tend to start fast and run fast. The cost is a build step every time you change the code. You also need
a separate build for each kind of processor. But many mistakes get caught during the build before the program ever
runs. C, C++, Rust, and Go work this way. The second way is to interpret. A program called an interpreter reads your
code and carries out each step as it reaches it. There's no build step. You write it and you run it. The same code
runs anywhere the interpreter runs. The cost is that the translating happens while the program runs, every single
time. So, a pure interpreter is usually slower. Now, a quick question. Which of these two gives you errors before the
program even starts? Take a second. It's the compiler because it reads everything before anything runs. An interpreter
finds many mistakes only when it reaches that line. The third way mixes the two. It uses a just in time compiler or JIT
for short. The program starts in a slower mode, often by interpreting. Meanwhile, the JIT watches which parts
run the most. When a part has run many times, the JIT compiles it into machine instructions. From then on, that part
runs fast. So, the first trip through a busy loop is slow and later trips are quick. You get much of a compiler's
speed and you skip the build step. The price is a warm-up period and extra memory for the JIT itself. The runtimes
behind Java and JavaScript work this way. That's the slow start from the Java service. The busy parts of the code
hadn't been compiled yet. How long the warm-up lasts depends on the runtime and on the work. Real languages often mix
these ideas. Many of them first turn your code into an in between form called byte code. Then that bite code is
interpreted or compiled by a jit. Java has a build step that makes byte code. Python makes byte code quietly every
time you run your code. So treat the three ways as a way to think, not as boxes every language fits into. Here's
the practical side. If a fresh release feels slow, give the jit a minute before you start tuning. And if a fast start
really matters, let that guide your choice of language. A small tool that runs and quits is a good example. So
here's what to take away. A compiler translates once before the program runs. An interpreter translates as it goes. A
JIT translates the parts that run the most. The runtime does more than run your code. In most languages, it also
cleans up the heap for you. Remember the heap from the start of the course? It's the storage room for data that outlives
the function that made it. You also met the short version of how it gets cleared out. The garbage collector frees what
your program can no longer reach. This lecture shows how it decides what that is. First, why have a collector at all?
In some languages like C, you clear the room yourself. You ask for memory and you must give it back when you're done.
Forget and you get a memory leak. Give it back twice or keep using it after giving it back and the program can
damage its own data. Those are some of the hardest bugs in software. So most modern languages do the cleanup for you.
And there are two main ways it works. The first way is to follow references. The collector starts from everything the
program can reach directly. That means the variables on the stack and global values that live for the whole program.
These starting points are called the roots. The collector follows every reference from the roots and marks each
object it reaches. Then it follows the references from those objects and keeps going. When it's done, anything on the
heap that wasn't marked can never be used again. So its memory is freed. This is called tracing garbage collection.
Java, C, Go, and JavaScript all use versions of it. The second way is to count. Every object keeps a count of how
many references point at it. Each new reference adds one. Each reference that goes away takes one off. When the count
reaches zero, the object is freed right away. This is called reference counting. Now try one. Two objects point at each
other and nothing else points at either of them. With reference counting, are they freed? Pause and think. They're
not. Each one still has a count of one from the other. So neither count ever reaches zero and both stay in memory
forever. That's the weak spot of reference counting. A loop of objects keeps itself alive. A tracing collector
doesn't have that problem. It only asks whether the roots can reach an object. Nothing reaches the pair, so both are
freed. Real languages deal with loops in different ways. Python counts references and also runs a separate check that
finds and frees loops. Swift counts references and has no tracing collector. So in Swift, you break a loop yourself.
You mark one side of it as a weak reference, which doesn't add to the count. In short, a tracing collector
follows references from the roots and frees whatever it never reaches. Reference counting frees an object when
nothing points at it. But a loop of objects can keep itself alive. At the start of the course, you met a service
whose memory climbed every hour, even with a garbage collector. You already know the short reason. Something still
points at old data, so the collector has to keep it. Now you can watch that happen one step at a time on a tiny
heap. A function is handling a checkout. Its stack holds a variable that points at an order. The order points at its
customer. Off to the side, there's a session and a shopping cart left over from an old request. They point at each
other and nothing else points at them. The program also keeps a cache. It's a map held in a global variable, so it
lives as long as the program does. That map still holds an old session from yesterday. No code will ever use it
again. Now the collector runs. Which of these objects survive? Pause and work it out. Start at the roots. From the stack
variable, the collector reaches the order and marks it. The order leads to the customer, so that's marked two. From
the global variable, it reaches the cache and then the old session inside it. Both are marked. Nothing reaches the
session and cart pair. So, both are freed even though they point at each other. And the old session in the cache
survives. The program is done with it, but the cache still holds a reference to it. So, the collector has to keep it.
That one is a leak. Notice that the pair which pointed at each other was freed. And the one that looked harmless was the
leak. It's the growing cash from the start of the course, now seen from the collector's side. The collector did its
job. The reference was the problem. So, how do you find the reference in a real program? Take a heap snapshot. It's a
picture of every object in memory and what holds on to each one. Take two, an hour apart, and compare them. the kind
of object that keeps growing and the collection holding it points straight at the leak. One warning about the memory
graph after a collection. Many runtimes keep the freed memory ready to reuse it. They don't hand it back to the operating
system. So memory that stays high after a busy hour isn't proof of a leak. Steady growth hour after hour is the
warning sign. The collector has one more cost. Some collectors pause the program for a moment while they work. For most
apps, nobody notices, but a game or a screen that shows live prices can feel those pauses. To keep them short, many
collectors split the heap by age. Most objects are used briefly and thrown away. So, the collector checks the young
objects often, which is cheap. It checks the old, longived ones much less often. Most runtimes can also tell you when the
collector ran and for how long. So if a program stalls now and then under heavy use, check that first. So when memory
looks wrong, check three things. Is it growing steadily or just staying high? What does a heap snapshot say is holding
on? And is the collector pausing the program too often? Memory is one thing the runtime handles for you. Doing
several things at once is mostly left to you. Think about the server behind an online shop. Many customers use it at
the same time. One is browsing while another is paying. If the server served them one at a time, everyone would wait
behind the slowest customer. So, one program needs to do several things at once. Your computer does the same thing
with all the programs you have open. Both rely on two ideas from the operating system. They're called
processes and threads. A process is a running program with its own memory. The operating system keeps each process's
memory separate. So, one process normally can't read or damage another one's memory. And if one process
crashes, the others usually keep running. Processes can share memory, but only if they set it up on purpose.
Otherwise, they pass data through files or messages. A thread is one line of work inside a process. One process can
have many threads. They all share the same memory, but each one has its own stack. Think of a process as a house and
threads as the people living in it. Each house has its own walls. Inside one house, everyone uses the same kitchen.
Threads are cheaper to start than processes, and they share data just by reading the same variables. That makes
them useful for a server with many customers at once. It's also how an app stays responsive while it downloads
something. Now, a question. Two threads in the same process both use one shopping cart object. One adds an item
while the other reads the total. Can that go wrong? Take a second. It can. Remember two variables pointing at one
object from the start of the course? A change through one shows up through the other. Threads are the same except now
both are using the object at the very same moment. So sharing memory is what makes threads useful. It's also what
makes them dangerous. Languages handle threads in different ways. Java, C, Go, and C++ let threads really run at the
same time on different cores. A core is one of the processing units inside the processor. Most processors today have
several. Standard Python works differently. It has a lock called the global interpreter lock or GIL for
short. It lets only one thread run Python code at a time. So threads help Python with waiting, like waiting on a
network, but they don't help with heavy computing on several cores. Newer versions of Python offer an optional
build without the GIL. JavaScript runs your code on one thread. Extra workers can run other JavaScript in parallel,
but each one has its own memory, and they talk by passing messages. A process has its own memory. Threads share one
process's memory. That sharing makes threads fast, and it's exactly where the danger starts. Here's what that danger
looks like in real code. The shop's server keeps one shared counter of today's orders. Two orders arrive at the
same moment, each on its own thread. Each thread adds one to the counter. Adding one looks like a single step.
It's really three. Read the counter. Add one. Write it back. Now watch two threads do it. The counter starts at
100. Before I go on, what should it end at? And could it end anywhere else? Take a second. It should end at 102. But
here's one way it can go. Thread A reads 100. Before A writes, thread B also reads 100. A adds one and writes 101. B
adds one and also writes 101. Two orders happened. The counter only went up by one. one order was lost from the count.
This is called a lost update. The bug is called a race condition. The result depends on the exact timing of the
threads as if they were racing each other and that timing changes from run to run. A race needs three things to be
true. Two or more threads use the same changeable data at the same time. At least one of them writes to it and
nothing makes them take turns. Take away any one of the three and the race can't happen. That's also why the tests
passed. They sent one request at a time, so there was never a second thread to collide with. Here's how strange it
gets. Say two threads each add one to the counter a million times each. You'd expect 2 million. Run it and you might
get 1,400,000. Run it again and you get a different number. Each run, the threads take turns
in a different order, so a different number of updates is lost. Now add a print statement inside the loop to see
what's going on. Often the bug disappears. Printing is slow, so it changes the timing. The threads stop
colliding as often. A debugger does the same thing because it pauses threads. So the act of looking changes the timing
the bug depends on. A lost update isn't even the worst case. In C and C++, a race like this on ordinary data is
called undefined behavior. That means the language makes no promise at all about what happens. The program might
lose an update or do something much stranger. Races are hard to catch, and it's not about skill. Code with one
thread does things in one order, so you can read it top to bottom. Code with many threads has a possible order for
every way the threads can take turns. The number of possible orders grows very fast. So, testing alone can't prove the
code is safe. The failing order might show up once in a million runs. Whenever threads share changeable data and one of
them writes, the timing decides the result. If nothing makes them take turns, updates will eventually get lost.
So, how do you make threads take turns? Every fix for the lost update comes down to one idea. Only one thread at a time
may be inside that read, add, write. The most common fix is a lock. Only one thread can hold the lock at a time. So
only one thread can touch the counter at a time. Here are the same two orders with a lock. Thread A takes the lock. It
reads 100, adds one, and writes 101. Then it lets go of the lock. Meanwhile, thread B has been waiting. Now it takes
the lock, reads 101, and writes 102. Nothing is lost. A lock only works if everyone uses the same one. Every piece
of code that touches the counter has to take that same lock. For a simple counter, most languages also offer an
atomic increment. Atomic means it can't be split. It does the read, the add, and the write as one step that no other
thread can get in between. Code that stays correct when many threads use it at once is called thread safe. But locks
bring a bug of their own. The shop also moves money between customer accounts. To move money safely, the code locks the
account the money comes from first. Then it locks the account the money goes to. Now two requests arrive at the same
moment. One moves money from account one to account 2. The other moves money from account 2 to account one. What happens?
Pause and think it through. The first thread locks account one. The second thread locks account two. Now the first
thread needs account two, so it waits. And the second thread needs account one, so it waits, too. Each one waits for the
other. Neither ever lets go. Both wait forever. This is called a deadlock. The program just stops. There's no error and
no crash. It simply never finishes. The fix is a simple rule. Always take locks in the same fixed order. Here, that
means locking the lower account number first. Now, both transfers start by locking account one. Whichever thread
gets it first does its whole transfer. The other one waits its turn and then does the same. When every thread takes
locks in the same order, nobody can end up waiting in a circle. Locks work, but every lock is a place where threads
wait. And each extra lock is another chance for a deadlock. So many teams try to design code that doesn't need locks
at all. How? Don't share changeable data between threads if you can avoid it. Give each thread its own data. Let
threads pass messages to each other. And use values that can't be changed once they're made. Then there's nothing for
two threads to change at once. When sharing can't be avoided, use the thread safe tools your language already gives
you. And keep the shared part as small as you can. So here's what to take away. A lock or an atomic step makes threads
take turns. Taking locks in one fixed order stops deadlocks. And the safest shared data is no shared data. Threads
are one way to serve many customers at once. There's another way, and it doesn't need a thread for each one.
Here's a strange site. A busy server answers very slowly, but its processor is mostly idle. It isn't working hard.
So, what is it doing? Follow a single request to find out. A customer places an order. Your code asks the database
for the customer's record. Then, it calls a payment service to charge their card. Time that request and you'll find
it spends almost all of its time waiting. The network and the disk are far slower than memory. While the
answers travel, the processor has nothing to do. So there are two kinds of work. Some work is waiting like reading
a file, asking a database or calling another service. That's called IO bound. IO stands for input and output. And here
they set the pace. Other work is computing like resizing a photo or checking a password. That's called
CPUbound because the processor sets the pace. The simple way to serve many users is one thread per request. Each thread
runs its request from top to bottom. While it waits, it just sits there blocked. That works, but threads aren't
free. Each one has its own stack, so it costs memory. And the operating system spends time switching between threads.
Thousands of mostly idle threads cost a lot just to wait. For a better way, think of a restaurant. In one
restaurant, every table gets its own waiter. The waiter takes the order, then stands by the kitchen until the food is
ready. In the other restaurant, there's one waiter. The waiter takes an order and hands it to the kitchen. Then, the
waiter goes to take the next table's order. When a dish is ready, the kitchen rings a bell and the waiter brings it
out. The kitchen does the slow part. The waiter never stands still. That second restaurant is an event loop. In a common
design, there's one thread and a queue of tasks that are ready to run. The loop takes a task and runs it until the task
has to wait. Then the task hands the waiting to the operating system and steps aside. The loop moves on to the
next ready task. Later, the operating system says the answer has arrived. The rest of the waiting task goes back in
the queue ready to run. That remaining part is called its continuation. Now let's time it. These numbers are
examples, not measurements. Three requests arrive together. Each one needs a database call that takes 100
milliseconds. With one thread doing them one after another, that's 300 milliseconds. How long does the event
loop take? Pause and work it out. The loop starts request one, sends its query, and moves on. It does the same
for two and three. That takes a millisecond or two. Now all three queries are waiting at once and the
thread is free. About 100 milliseconds later, the answers come back and each request finishes. So it's about 100
milliseconds in total plus a little extra. One thread did the work of three. But notice what it saved. It saved
waiting time, not computing time. An event loop helps with the first kind of work, not the second. So when a server
is slow but its processor is mostly idle, the work is waiting. That's where an event loop helps most. So how do you
write code that steps aside while it waits? Languages found three answers one after another. The first answer was
callbacks. You hand over a function that says when the answer arrives, run this. That works for one step, but chain a few
together and you get code nested inside code nested inside more code. It's hard to read. Promises came next. Some
languages call the same idea a future. A promise is an object that stands for an answer that isn't here yet. You attach
the next step to it instead of nesting. Then came async and await. It's a nicer way to write the same thing. Await means
if the answer isn't ready, pause this task here and let other tasks run. So the order code reads top to bottom
again. It awaits the customer, then it awaits the payment. But underneath it's still the event loop. Now the first
trap. Picture a server with one thread and an event loop. One endpoint does a calculation that takes 2 seconds. What
happens to every other user during those two seconds? Pause and decide. They all wait. Nobody gets an answer, not even
for a simple page. Here's why. The calculation never reaches an await. So it never steps aside. The one thread is
busy the whole time. That's called blocking the loop. A call that waits the old way does the same damage. An old
style file read is one example because it holds the thread until the file arrives. The fix has two parts. Move
heavy computing to a separate thread or process so the loop stays free. And for anything that waits, use the version
built for async, the one you can await. The second trap is about speed. A slow calculation is just as slow with a
weight in front of it. It's easy to think Async makes everything faster. It doesn't. Async makes waiting cheap. It
doesn't make computing fast. The third trap is the most surprising. With only one thread, it seems races should be
gone, but other tasks can run at every await. Here's one. A task reads today's order count and gets 100. Then it awaits
while it saves the new order. When it wakes up, it writes 101. But while it was paused, a second task also read 100.
So both tasks write 101 and an order is lost. It's the same lost update as with threads. Here, every await is a place
where another task can get in between. So treat every await as a pause where anything can change. Read shared data
again after an await or keep the read and the write together with nothing in between. Different languages run async
code in different ways. Node.js JS runs JavaScript on one thread with an event loop and so does Python's async library.
C and some other languages also have async and a wait, but they may pick up a pause task on a different thread from a
pool. So remember what await does and doesn't do. It lets one thread wait on many things at once. It doesn't speed up
computing and it doesn't remove races. When a server feels slow, ask one question first. Is it waiting or is it
computing? You've now seen each of these ideas on its own. Here's what happens when they all show up in one place. This
case is made up, but it's built from bugs that show up in real code all the time. A team has an endpoint called get
customer report. An endpoint is one address in a web service that other code can call. This one lists every customer
with their orders and their totals. It also flags any customer whose email is on a blocked list. At launch, it
answered in under a second. A year later, it took most of a minute. Some totals were off by a scent. And the
server's memory grew for days until someone restarted it. Here's how the team worked through it in the order they
did it. The first move wasn't reading code. It was measuring. They ran the report on test data with 500 customers.
Then they tried 1,000 and then 2,000. 500 took about 1 second. 1,000 took about 4. 2,000 took about 16. What shape
is that? Pause and work it out. Doubling the customers made it four times slower. That's quadratic. So the answer to how
does it grow was clear. A faster server wouldn't fix it. Every run would get a little quicker, but the shape would stay
quadratic. So they looked for work hidden inside other work. Before I tell you, which line would you look at first?
There was no loop inside a loop anywhere in the code. There was one loop over the customers. Inside it was one simple
looking line. It checked whether the customer's email was in the blocked list. The blocked list was a plain list
and it grew along with the customers. Checking a list means comparing against each item until there's a match. So that
one line was a hidden loop. It's the same mistake as the customer import from the hashmap lecture. A thousand
customers checked against a thousand blocked emails is up to a million comparisons. The fix was a hash set.
They built it from the list once before the loop. After that, each check took about one step. So that part went from
quadratic to linear. The time dropped, but it still grew too fast. So they asked the second question, where does
the data live? Each customer's orders lived in the database on disk. For every customer, the code ran one query to
fetch that customer's orders. And the orders table had no index on customer ID. So every one of those queries read
the whole table. They added an index on customer ID. It's usually a B tree kept sorted. Now, each query could usually
jump straight to one customer's orders. Then they fix the pattern itself. One query per customer is called the n +1
query problem. One query gets the customers and then there's one more query for each customer. Every query
pays for a trip to the database and back. So they grouped them. Each query now fetched orders for a few hundred
customers at once. Both fixes came from the same habit. Measure first, then ask how it grows and where the data lives.
The report was fast. now. But two problems were left. Some totals were off by a cent and the memory kept growing.
The team took them one at a time. First, the cents. They made the error easy to repeat. They took one day's orders and
added up each customer's total by hand in whole cents. Then they compared that with what the report printed. A handful
of customers were off by exactly 1 cent. Then they found how the amounts were stored. Each one was a dollar amount
with a decimal point stored as floating point. Before I go on, why would that be off by a cent? Think back to the start
of the course. Take a second. Floating point stores numbers in binary. And most decimal fractions like 10 cents can't be
written exactly in binary. It's the same reason 0.1 + 0.2 isn't quite 0.3. So each amount was very slightly wrong.
Add up thousands of them and those tiny errors add up too. Now and then rounding pushed a total to the wrong cent. The
fix was to store and add money as whole cents. Cents are whole numbers, so they add exactly. The report turned them back
into dollars only when it showed them on screen. Next came the memory. The team looked at a graph of the servers memory
over a week. It grew steadily and never flattened out. It kept growing even at night when hardly anyone used the app.
That steady growth is the warning sign of a leak. So they took a heap snapshot. It showed one map holding almost
everything. At some point, someone had added a cache to speed up the report. It was a map stored at the top level of the
program, so it lived as long as the program did. Every report ever made went into it, filed under the date and the
customer, and nothing ever came out. Each new day brought a whole new set of entries. People had assumed the garbage
collector would clean up, but the collector only frees objects that nothing can reach, and the cash still
held a reference to every report, so nothing could be freed. That's how a program with a garbage collector still
leaks. The fix was a cache with a size limit. They used an LRU cache, the one built from a hashmap and a doubly linked
list. When it's full, it throws out the entry nobody has used for the longest time. Memory went flat. They watched the
graph for a week to be sure. Two lessons came out of it. Wrong cents point to floating point. So keep money in whole
sense. And memory that only grows points to something holding on. So look for the collection that never lets go. Two bugs
were left in the report endpoint. A counter came up short when many people used the app and some blocked customers
got through. Neither bug ever showed up on a laptop. First, the counter. A dashboard showed how many reports had
run today. In the live app, it started reading low. The team compared it with the number of rows in the reports table.
The table was always higher. To make it happen on purpose, they ran a load test. That's a test that sends many requests
at once, like real traffic. They sent 200 report requests together. The counter came back short every time by a
different amount each run. What kind of bug gives a different wrong answer every run? Pause and decide.
It's a race condition. The server handled requests on several threads and they all added one to the same counter.
It's the lost update from earlier. Two threads both read 40, both write 41, and one report disappears from the count.
The laptop tests only sent one request at a time, so the race never happened. The fix was an atomic increment, so the
three steps can't be split. A lock would also work. They ran the same load test again, and the counter matched the
table. The last bug was the strangest. Now and then, a blocked customer got through without being flagged. At first,
nobody could make it happen on purpose, so the team added a log line. It printed each email at the moment of the blocked
check. In the bad cases, the email was full of stars. Here's what happened. A helper called format customer made a
version of the customer for display. That version hides most of the email behind stars. But the helper didn't make
a new object. It changed the email on the customer object it was given. And it had been given a reference to the same
object, not a copy. Remember two names pointing at one object? It's that bug. So, every other part of the code saw the
starred email, too. On one path through the code, the formatting ran before the blocked check. So, the check looked for
the starred email, found no match, and let the customer through. The fix was to have the helper build a new display
object, and leave the original alone. They also added a small test. It checks that formatting a customer leaves the
original unchanged. Now, look at what the team didn't do. They didn't guess and they didn't
rewrite the whole endpoint. Each time they measured first. They asked how it grows and where the data lives. Then
they changed one thing and measured again. Fixing one bug never fixed the others. Each one needed its own
measurement or its own test. In the end, one scary endpoint turned into seven ordinary bugs. And each one had a name
you now know. Let's look back at everything this course covered from start to end. It began with how a
computer stores data. Everything is bits grouped into bytes and counted in binary. Every number type has a limit it
can wrap past. Text is just numbers with an agreed meaning. Floating point can't store most decimal fractions exactly. So
money belongs in whole sense. Then the data went into memory. The cache keeps nearby data close to the processor. The
stack holds function calls and the heap holds data that has to last longer and a variable holds either a value or a
reference to data that others may share. The second module was about how work grows as data grows. Big O names that
growth in six common shapes from constant up to exponential. Loops reveal the shape and memory grows too, not just
time. Recursion handles problems inside problems and remembering answers makes it fast. Good sorting takes n login and
binary search halves the work at every step. Then came data structures ways of arranging data so some jobs are fast.
Arrays keep items side by side. Linked lists chain them with pointers. Stacks serve the newest item first and cues
serve the oldest and the right structure depends on what the code does most. The fourth module covered the structures
that find things fast. Hashmaps find by key in about one step. Balance trees keep things sorted. Heaps always know
the most urgent item. Graphs connect anything to anything. And real systems combine them in caches and in database
indexes. The last module looked at code as it runs. Code gets compiled, interpreted or compiled while it runs. A
garbage collector frees only what nothing can reach. Threads share memory, so races can lose updates, and locks
make threads take turns. Async code serves many people while it waits. So why learn all of it? Because every
language, framework, and AI tool sits on these same ideas. Tools change every few years. These ideas don't. Learn them
once and they stay useful for your whole career. Here's what changes for you now. When you read code, you can tell how it
will behave once the data gets big. Choosing a data structure becomes a decision you can explain. A slow
endpoint stops being a mystery. Strange bugs get names. And when code comes from a teammate or an AI tool, you can judge
whether it will hold up. What should you start next? Take one small step this week. Pick one structure like a hashmap
and build it once in your own language. That's what makes the costs stick. Then pick a direction. If interviews are
coming up, practice problems one topic at a time and say how the work grows before you write any code. If you want
better code at work, ask what each line inside a loop costs. And if you want to go deeper, good next topics are system
design, operating systems, and databases. Each one builds on what's here. Through all of it, two questions
kept coming back. How does it grow? And where does it live? When code is slow, ask the first one. When code is strange,
ask the second. You made it to the end. Well done. A lot of working developers never sit down and learn this. These
ideas won't go out of date. Keep asking the two questions and they'll keep helping you in every project you work
on. Thanks for watching. Good luck.
As data grows, algorithms with poor scalability (like those with nested loops) can cause an explosion in the number of operations. For example, an O(n²) algorithm comparing every pair increases from 10,000 comparisons for 100 records to 10 billion for 100,000 records, turning a fast operation into one that takes minutes.
Computers store numbers in binary (base 2). For signed numbers, they use two's complement, where the leftmost bit represents -128, leading to overflow when adding beyond the range (e.g., 127 + 1 becomes -128). Decimal fractions like 0.1 cannot be represented exactly in binary, so calculations like 0.1 + 0.2 may produce small errors, which is critical to watch for in money or equality checks.
Big O notation describes how the time or memory requirements of an algorithm grow in the worst case as input size increases. It classifies algorithms into categories like O(1) (constant time), O(n) (linear), O(n²) (quadratic), or O(log n) (logarithmic), helping developers choose efficient algorithms, especially when scaling to large data sets.
Arrays offer O(1) read/write by index but O(n) insert/delete in the middle. Hashmaps provide average O(1) lookups but no order and can degrade with collisions. Balanced trees (BST) achieve O(log n) for search, insert, and delete, making them good for ordered data. Graphs optimize for connections with algorithms varying based on whether finding shortest paths or reachability.
The three common bugs are: 1) Shared references, where copying an object copies only the reference to nested objects—fix by deep cloning. 2) Text encoding mismatches, where UTF-8 and ISO-8859-1 conflict—fix by always knowing the encoding at boundaries. 3) Overflow, where numbers exceed their type's range—fix by using 64-bit integers for counters, file sizes, or money, and understanding how your language handles overflow.
RAM is volatile and fast, ideal for active computations like a whiteboard, while disk is non-volatile but much slower, suited for persistent storage like a notebook. Using disk for frequently accessed data can dramatically slow down a program, so developers should keep working data in RAM and design algorithms to minimize disk I/O.
By analyzing the memory layout, algorithm choice (e.g., replacing an O(n²) operation with an O(log n) tree lookup), and threading issues that cause contention. All concepts from the course—Big O analysis, data structure selection, and memory hierarchy—come together to pinpoint why the code slows under load and how to refactor it for better performance.
Keep this summary
Save it to LunaNotes and it becomes a real note in your library — editable, searchable, and ready to turn into flashcards or a diagram. Free to start.
Save to LunaNotesOr summarise for another video.
32K+ people have turned 65K+ videos into notes
“Very useful tool. I'm using it for the last couple weeks and I'm loving it so far. Makes learning on YouTube a great experience.”
This summary and transcript were automatically generated using AI with the Free YouTube transcript summary tool by LunaNotes.
Related summaries
Comprehensive Guide to Core Data Structures and Algorithms
Explore foundational concepts in data structures, computational complexity, and advanced algorithms. This guide covers arrays, linked lists, stacks, queues, priority queues, union-find, trees, hash tables, Fenwick trees, suffix arrays, balanced BSTs, and indexed priority queues, with insights on implementation and performance optimization.
8 Essential LeetCode Patterns to Solve Coding Problems Efficiently
After solving over 500 LeetCode problems, the key insight is to focus on repeating patterns rather than individual solutions. This video outlines 8 fundamental patterns—including sliding window, subset, modified binary search, and two-pointer—that can simplify complex coding challenges and improve problem-solving speed.
CS50 Harvard: From Binary Basics to Building Interactive AI Chatbots and Games
Discover Harvard's CS50 introductory course, exploring foundational computer science concepts from binary data representation to AI programming and game development with Scratch and Python. Learn how fundamental algorithms, data structures, and coding techniques empower you to solve complex problems and create dynamic applications, including chatbots and interactive games.
Understanding Time and Space Complexity: A Comprehensive Guide to Big O Notation
Explore the concepts of time complexity, space complexity, and Big O notation with practical examples.
Comprehensive Overview of Algorithms and Data Structures Course
This course provides an in-depth exploration of algorithms and data structures, focusing on sorting and searching algorithms. It covers key concepts such as recursion, big O notation, and the implementation of various algorithms including merge sort, quick sort, and linear search, using Python as the primary programming language.
Most viewed summaries
A Comprehensive Guide to Using Stable Diffusion Forge UI
Explore the Stable Diffusion Forge UI, customizable settings, models, and more to enhance your image generation experience.
Kolonyalismo at Imperyalismo: Ang Kasaysayan ng Pagsakop sa Pilipinas
Tuklasin ang kasaysayan ng kolonyalismo at imperyalismo sa Pilipinas sa pamamagitan ni Ferdinand Magellan.
Mastering Inpainting with Stable Diffusion: Fix Mistakes and Enhance Your Images
Learn to fix mistakes and enhance images with Stable Diffusion's inpainting features effectively.
Pamamaraan at Patakarang Kolonyal ng mga Espanyol sa Pilipinas
Tuklasin ang mga pamamaraan at patakaran ng mga Espanyol sa Pilipinas, at ang epekto nito sa mga Pilipino.
How to Install and Configure Forge: A New Stable Diffusion Web UI
Learn to install and configure the new Forge web UI for Stable Diffusion, with tips on models and settings.
Found this summary useful?
Take it with you. One click puts it in your own LunaNotes library.
Save to LunaNotes