Lecture III · Data Structures & Algorithms
How fast is it, really?
Two programs can both be correct and still be worlds apart: one finishes before you lift your finger, the other is still running when you come back from lunch. This lecture is about how we talk about that difference precisely, without lying to ourselves about what a stopwatch actually measures.
Put a stopwatch on it
The honest way to start is not with a theorem but with an experiment. Write a function, feed it an input of size n, and time it. Then double n and time it again. The number you care about is not the raw seconds. It is the ratio: when the input doubled, did the time roughly stay put, double, quadruple, or explode?
That ratio is the whole game. A function whose time barely moves when n doubles is a different animal from one whose time quadruples every time. You do not need to know the machine, the language, or the phase of the moon to see the difference. You just need to watch how the time responds when you turn the one knob that matters.
The trouble is that a stopwatch is a noisy instrument. Your operating system decided to check for email in the middle of the run. The cache was warm the second time. Another process stole the core. Run the same code three times and you get three numbers. So the stopwatch tells you something real, but it buries it under noise, and it ties the answer to this laptop on this afternoon. We want a measure of the algorithm, not of the weather.
Stop trusting the clock, start counting
Here is the move that rescues us. Instead of timing the program, count the operation that does the most work. Pick the line that runs the most often, the comparison or the swap or the copy at the heart of the loop, and count how many times it runs as a function of n. That count does not care about your cache or your email. It is a property of the algorithm.
Counting also has a lovely side effect: the small stuff washes out. Suppose one algorithm does comparisons plus 12, and another does . For small n the constants and the leftover terms fumble around and matter. But push n up and the shape of the dominant term swallows everything else. The “plus 12” becomes a rounding error. This is why we get to be a little careless on purpose: we keep the term that grows fastest and throw the rest away.
def count_pairs(data):
ops = 0
zeros = 0
for i in range(len(data)):
for j in range(i + 1, len(data)):
ops += 1 # the dominant operation
if data[i] + data[j] == 0:
zeros += 1
print("checked", ops, "pairs")
return zeros
Count the pairs and you find the inner line runs times. Nobody sane carries the “minus n over 2” around. We say it does about work, and soon we will say even less than that. But notice what we did: we replaced a stopwatch with arithmetic, and the arithmetic is exact and portable.
Version A looks innocent, but result + [x] does not extend the list in place.
It builds a brand new list and copies every element that was already there. On step k it
copies about k items, so the total work is , which is that same
shape. Version B just drops one element on the end each time, n times
total. One is quadratic, the other linear. Run the harness and watch the columns: when n
doubles, the append column doubles, and the concat column roughly quadruples.
Big-O, said plainly
Now we can say what all this notation means, and it is less mysterious than it looks. When we write that an algorithm is , we are making one claim: for large enough n, its operation count is at most some constant times . That is it. Big-O is an upper bound that kicks in once n is big, and it is deliberately blind to constant factors.
Three habits fall straight out of that definition. First, we drop constant multipliers: and and are all , because a constant is exactly what the bound is allowed to absorb. Second, we drop lower-order terms: is , because past some n the squared term dominates and the rest fits under a slightly larger constant. Third, we only promise anything for large n. Big-O says nothing about . It is a statement about the trend as inputs grow, which is precisely the trend our doubling experiment was chasing.
It is worth being clear about what O does not say. It is an upper bound, not a promise of tightness: technically every linear algorithm is also , because a smaller bound is also a valid larger one. In practice we quote the smallest honest bound we can, so when someone says an algorithm is they mean n is a snug fit, not just a legal one. And O describes a class, not a running time in seconds. It tells you the shape of the growth. The shape is what survives when you change machines, and the shape is what we can actually reason about.
The Fairfield Way race
Growth classes stay slippery while they stay abstract, so let us put them down on ground you actually walk. Fairfield Way is the brick spine of this campus, the stretch that runs from the Student Union down past Wilbur Cross toward Mirror Lake, and ten minutes before the hour it is a river of people. Call the number of students on it n. Every class in this lecture is an errand you could run along that walk, and the errands feel different in exactly the way the classes are different.
Errand one: step onto the Way and ask the first student you meet what time it is. That is one question. It is one question if forty people are out and one question if four thousand are, because you never look past the first face. The size of the crowd is not in your bill at all. That is constant time, : work that does not know how big n is.
Errand two: walk the whole length and nod once to every student you pass. Now the crowd is your bill exactly, n nods. Twice the crowd, twice the nodding, and the ratio when n doubles is 2. That is linear, , and notice that the walking itself, the three hundred-odd seconds it takes to get from one end to the other on an empty afternoon, has quietly become a constant sitting next to it.
Errand three is the one nobody should agree to. Instead of you greeting everyone, every pair of students on the Way shakes hands with each other. The first person has hands to shake, the second has still unmet, and so on down to the final pair, so the total is , which is . That is the same triangular sum we counted for the nested-pair scan two sections ago, and it is quadratic, . Double the crowd and the handshaking roughly quadruples.
Between the nod and the handshake sits the errand that describes every good sorting algorithm. Suppose you want the whole Way sorted into height order. Run it as a tournament: pair everybody off and compare, then merge the sorted pairs into sorted fours, the fours into eights, and so on. Every round touches every student exactly once, and there are only rounds, because the group sizes double each time. That is , and the point of the metaphor is that it feels much more like nodding than like handshaking.
Now the arithmetic, because this is where the metaphor has to earn its keep rather than just sound nice. Take a busy class change, . Asking one person the time is one question. Nodding to everyone is 2000 nods. The tournament runs eleven rounds, since , for about 22,000 comparisons. And the handshakes come to . Those last two numbers are the lesson. The tournament costs about eleven times a single pass; the handshakes cost about a thousand times a single pass, and ninety times the tournament. is linear with a modest fine attached. is a different way of life.
Why the constants stop mattering
Students resist the “throw the constants away” move, and they are right to, so let us argue it with the walk rather than assert it. Constants are real. Suppose the nodding is done by someone who dawdles, ten seconds a student, and that simply covering the length of the Way costs a flat 300 seconds whether it is deserted or packed. Suppose the handshaking is organised by a fanatic who has drilled the greeting down to one second flat. The nod plan then costs seconds; the handshake plan costs .
For a quiet walk the fanatic wins outright. At the handshakes take 190 seconds against the dawdler’s 500. The fanatic keeps winning all the way to (666 seconds against 670) and loses from onward. That crossover is precisely what big-O hides, and precisely what we said it hides on purpose: for small n the constants decide the race, and a quadratic with a good constant genuinely beats a linear with a bad one.
Push n up to a real class change and the hiding stops costing you anything. At the dawdler finishes in 20,300 seconds, a shade under six hours. The fanatic needs 1,999,000 seconds, about twenty-three days. And here is the part worth carrying out of this room: let the fanatic get ten times faster still, a tenth of a second per handshake, and the crossover moves only from 38 people to 228, while at 2000 the bill is still 199,900 seconds, well over two days against the dawdler’s six hours. A tenfold improvement in the constant bought about six times more crowd before the loss, and changed nothing about who loses. A constant factor buys you a bigger n before you are beaten. It never buys you the win. Only the shape does that.
So we throw the constants away not because they are unreal but because they move the crossover and leave the verdict alone. The term that grows fastest is the part that decides who is still shaking hands when the four o’clock crowd arrives.
The classes, in order
A handful of shapes come up again and again, and it pays to know them cold, from gentlest to most violent: constant , logarithmic , linear , linearithmic , quadratic , and exponential . Constant time does the same work no matter how big the input gets. Logarithmic time is the reward for halving the problem each step, the way binary search does. Linearithmic, , is the natural home of the good sorting algorithms. Quadratic is what a pair of nested loops over the same data buys you. And exponential is the cliff: it is usable for tiny n and hopeless almost immediately after.
The problem with drawing these on ordinary axes is that they refuse to share a frame. Plot them linearly and and shoot off the top while constant, , , and all pile up on the floor, indistinguishable from each other and from zero. The fix is a log-log plot: put the log of n on one axis and the log of the count on the other. On those axes something magical happens. Every power law becomes a straight line, and its slope is its exponent. Constant is flat, linear climbs at slope one, quadratic at slope two. The classes stop overlapping and fan out into a lineup you can read at a glance. The exponential is the giveaway: it is not a power law, so it does not straighten out, it just curves up and leaves the chart.
Play with the next plate before reading on. Toggle between linear and log-log axes and feel how useless the linear view is and how the log-log view separates everything. Then hide the names and try to name the curves from their shapes alone. The plate is dressed as the walk: read n as the students out on Fairfield Way, and under the legend you will find the six errands, one per curve, listed gentlest first. Matching an errand to a curve is the same skill as matching an algorithm to a class, which is the skill this whole lecture is for.
Idealised operation counts on log-log axes. Each power law is a straight line; the exponential runs off the top. With JavaScript on you can switch to linear axes and play the guess-the-curve game. Read n as the number of students on Fairfield Way, and each curve as one errand you could run along it.
Once you have the lineup in your head, most cost questions become pattern matching. A single pass is linear. A loop inside a loop over the same data is quadratic. Halving the search space each step is logarithmic. You stop needing the stopwatch, because you can read the shape off the code.
What big-O quietly leaves out
Two cautions, so you do not overlearn the lesson. First, constants and lower-order terms are invisible to big-O but painfully visible on real inputs. An algorithm with a gigantic constant can lose to an one for every input you will ever actually run. Big-O tells you who wins eventually; eventually can be further away than your data ever reaches. This is why library sorts switch to insertion sort, an method, on small chunks: for tiny n the small constant beats the better shape.
Second, the same algorithm can have different costs depending on the input, not just its size. Searching an unsorted list might find the answer on the first try or the last, so we distinguish best, worst, and typical cases and usually quote the worst as our guarantee. Big-O is a powerful lens precisely because it throws away detail, but a good engineer remembers what got thrown away. Measure when it matters, count to understand why, and reach for the asymptotics to predict what happens when the input grows past anything you have tested. Those three tools, in that order, are the whole discipline.
Best, worst, and average
That last caution deserves a section of its own, because “the same algorithm can cost different amounts on different inputs” is the idea people most often skate past. Take the simplest search there is: walk an unsorted list from the front, comparing each item with your target, and stop the moment you find it.
The best case is one comparison: the target was in the very first slot. The worst case is n comparisons: it was last, or absent. Those two are not a constant factor apart, they are different classes, against . The average, if the target is equally likely to be anywhere, is about comparisons, which is still , the same class as the worst. So for linear search the honest one-word summary is : the worst and the typical case agree, and only the lucky best case is misleadingly cheap.
Insertion sort makes the spread starker. On a list that is already sorted it does a single clean pass, , because every element is at once in place. On a list sorted backwards it shoves every element all the way down, doing the full work. Its average over random inputs is quadratic too. Here the best case and the worst case live in different growth classes, and quoting one without saying which would be a lie by omission.
This is why the default guarantee we quote is the worst case. It is the promise that never breaks: no input you feed me will cost more than this. When someone says an algorithm is with no qualifier, they almost always mean in the worst case. The average case earns its keep in exactly the situations where the worst case is real but pathologically rare. Quicksort’s worst case is , yet we reach for it everywhere, because that worst case needs a cruelly arranged input that good implementations dodge, and its average is . Hash-table lookup tells the same story: if every key collides, on average, and the average is the number that describes your day. Best case we mostly ignore, because nobody ships a guarantee that depends on getting lucky.
Upper bounds, lower bounds, tight bounds
Big-O, remember, is only an upper bound: at most a constant times this, for large n. It has two siblings that finish the vocabulary. Big-Omega is the mirror image, a lower bound: an algorithm is when its count is at least a constant times g for large n, no matter how the wind blows. And big-Theta is the two clamped together: an algorithm is when it is both and , so g fits snugly from above and below at once. O is a ceiling, Omega is a floor, Theta is a fitted sleeve.
This is the honest way to say what we gestured at earlier, that we quote the smallest legal bound. Strictly, a linear algorithm really is : a loose ceiling is still a ceiling. What we usually want to communicate is the tight fit, and the tight fit is a Theta claim. When a textbook says merge sort is , it is being polite: what it means, and what is true, is that merge sort is , bounded both above and below by up to constants. We say O out of habit, and because it is the safe direction to be wrong in, but we almost always mean Theta.
The one place you must not fuse them is an algorithm whose best and worst cases differ, like insertion sort. It is , because no input costs more, and it is , because every input costs at least one full pass. There is no single Theta across all inputs, because the floor and the ceiling sit in different classes. You can still make a tight statement, you just have to name the input: on already-sorted input insertion sort is , and on reversed input it is . The bounds only close into a Theta once you have pinned down which case you mean.
The amortized bargain
Back in the very first plate, appending to a list came out as the cheap, linear way to build a sequence, one operation per element. That was a little too glib, and the truth is more interesting. A list is really a fixed-size block of memory. When it fills, there is nowhere to put the next item, so Python quietly allocates a bigger block and copies every existing element across. That copy is work, and it happens on some appends. So how can we possibly call append ?
The answer is the doubling trick, and it is worth counting. Python does not grow the block by one slot at a time, it grows it by a constant factor, roughly doubling. The appends that overflow, and so pay for a full copy, land at sizes 1, 2, 4, 8, 16, and so on: the powers of two. To reach n items you copy up to the last power of two below n, and that sum is itself less than . So n appends cost fewer than copies in total, no matter how the resizes fall. Spread that bill evenly and each append costs a constant on average. That averaged-over-the-sequence cost is what we mean by amortized: any single append might be expensive, but a long run of them cannot average to more than a constant apiece, because the rare expensive copies are bankrolled by all the cheap appends before them.
The doubling is load-bearing. If the list grew by a fixed ten slots instead of doubling, the copies would land every ten appends, each copying the whole array, dragging the total back up to the quadratic shape we have worked so hard to escape. Growing by a constant factor is exactly what keeps the amortized cost flat. Count it yourself in the next plate: tally the copies for a doubling array and watch the total stay under even as n runs to a thousand.
The checks · run against your code
# The first append needs no copy: capacity 1 already holds it. assert total_copies(1) == 0 # The second append is the first resize, copying the 1 item already there. assert total_copies(2) == 1 # By the third append we have copied 1 then 2, three copies in all. assert total_copies(3) == 3 # Filling to 8 costs 1 + 2 + 4 = 7 copies; appends 4..8 are free. assert total_copies(8) == 7 # Crossing to 9 triggers copying all 8 at once: 7 + 8 = 15. assert total_copies(9) == 15 # Even at 1000 appends the running total stays under 2n. That is the point. assert total_copies(1000) < 2000
Hint one
Track three quantities as you go: the running copies count, the current
size, and the current capacity. A resize happens only when
size has caught up to capacity.
Hint two
On a resize you copy every element currently stored, which is size of them,
and then capacity doubles. Between resizes, appends add nothing to the tally.
The solution
Walk the appends and only pay on overflow:
def total_copies(n):
copies = 0
size = 0
capacity = 1
for _ in range(n):
if size == capacity:
copies += size
capacity *= 2
size += 1
return copiesThe total never reaches , so averaged over n appends the cost is a constant: that is amortized. This same bargain is what lets Lecture IV’s deque grow cheaply at both ends. It is also our first glimpse of paying a little wasted space, the half-empty block left after a resize, to buy back a lot of time.
Space is a cost too
Everything so far has counted operations, which is a proxy for time. Memory is the other budget, and it wears the same notation. Space complexity asks how much extra room an algorithm needs as n grows, in the same O, Omega, Theta vocabulary. Summing a list needs one running total no matter how long the list is, so it is extra space. Building a reversed copy of the list needs a second list the same size, so it is . We usually count the extra space a method allocates, on top of the input it was handed, because the input was going to cost what it costs regardless.
Time and space are not independent knobs; very often you can spend one to save the other. The doubling list above already made the trade in miniature, wasting a half-empty block so that appends stay fast. The pattern has a name we will lean on hard in Lecture VII: memoization, where you keep a table of answers you have already computed so you never pay to compute them twice. That table is pure space, bought to erase repeated time. It is the same bargain as a sort that copies its input into scratch space to run faster, versus an in-place sort that guards its space at the cost of fiddlier code. Neither direction is simply “better.” The right question is which resource is scarce for the problem in front of you, and the whole point of having the vocabulary for both is to let you say the trade out loud instead of stumbling into it.
Count it yourself, then read the ratio
We opened by promising that the ratio is the whole game: double n, and watch whether the count holds steady, doubles, or quadruples. You now have the vocabulary to say what each ratio means, so let us close the loop and put the instrument in your hands. The next plate counts the dominant operation for three shapes at once, a single pass, a triangular double loop, and a halve-until-one loop, and prints the ratio of each count to the one before it.
Read the ratio column, not the raw counts. The linear shape settles on about 2.00: double the input, double the work. The triangular shape settles on about 4.00, the signature of a quadratic, because doubling n roughly quadruples . The halving shape barely moves, adding a single step every time n doubles, which is exactly what looks like from the outside. Change the sizes, add a shape of your own, and the ratios will name its class before you have finished writing its loops.
The ratio is doing the work a log-log plot did two sections ago, only in a column of numbers instead of a slope. A ratio near 2 is slope one, a ratio near 4 is slope two, a ratio near 1 is a nearly flat line. Same story read two ways: reach for whichever you can compute in your head. Now drive the counting the other direction. Instead of reading a class off a count, produce the count for a shape you are handed. Three loops this time, each running the full range, which is the canonical way to buy yourself a cubic.
The checks · run against your code
# cube_ops(1) is 1 assert cube_ops(1) == 1 # cube_ops(2) is 8 assert cube_ops(2) == 8 # cube_ops(3) is 27 assert cube_ops(3) == 27 # cube_ops(10) is 1000 assert cube_ops(10) == 1000
Hint one
Hold i and j fixed for a moment: the innermost loop for k in range(n) runs
exactly n times. There are n choices of j for each i, and n choices of i.
Hint two
So the innermost line runs n times, n times over, n times over again. That is , and the closed form is .
The solution
Return the closed form, or run the three loops and tally; both agree:
def cube_ops(n):
return n ** 3Three nested loops over the same n give , the cubic class, one storey up from the quadratic you counted for the triangular nest. Each extra full loop multiplies the work by another factor of n, which is why deep nesting turns expensive so fast.
Exercises
Classify each by its tightest big-O in terms of n, the length of
data. (a) A singleforloop overdatathat adds each element to a running total. (b) Two nested loops overdatathat print every ordered pair. (c) A loop that keeps halvingnuntil it reaches 1. Say which growth class each one lands in and why.Someone claims their function is because “there is only one loop.” The loop body, however, calls
x in dataon a list, which itself scans the whole list. What is the real running time, and what is the general lesson about hidden loops inside innocent-looking lines?An algorithm does exactly operations; a second does . Big-O says the first is and the second , so the first “wins.” For which values of n is the first actually faster? Find the crossover, and explain why big-O still made the right long-run call even though it hid this.
Write
count(n)so that it returns how many times the linetotal += 1runs in this nest:for i in range(n): for j in range(i): total += 1. Then, in one sentence, name the growth class of that count. You can solve it with a closed-form formula or by running the nest; the checks accept either.The checks · run against your code
# count(1) is 0 assert count(1) == 0 # count(5) is 10 assert count(5) == 10 # count(10) is 45 assert count(10) == 45 # count(100) is 4950 assert count(100) == 4950
python runs in your browser · first run downloads ~240 kbPlate VI TRIANGULAR COUNT · Implement count(n). The nest runs its inner line 0, then 1, then 2, ... up to n minus 1 times. Run to grade against four sizes. Hint one
For a fixed i, the inner loop
for j in range(i)runs exactly i times. So the total is .Hint two
That sum has a closed form: the sum of the first m whole numbers is . Here the top number is n minus 1, so the total is .
The solution
Return the closed form directly, no loop required:
def count(n): return n * (n - 1) // 2The count grows like , so the nest is , the quadratic class. This is the exact shape you counted for the nested-pair scan and for the slow list build earlier: nested loops over the same data are the canonical way to buy yourself a quadratic.
A function scans the pairs of a list looking for a duplicate and returns
Truethe instant it finds one, elseFalseat the end. Give its best case, its worst case, and the growth class of each. Which one would you quote as the algorithm’s cost, and why is the other one a poor guarantee to advertise?You append 1,000 items to a Python list one at a time. Explain, in terms of the doubling trick, why the whole run is work even though a handful of those appends secretly copied the entire list. Then say what would go wrong with the amortized cost if the list grew by a fixed 10 slots on each resize instead of doubling.
You want to know whether an array of n numbers contains two that sum to a target. Plan A sorts the array and walks two pointers inward: time, extra space. Plan B stores each number it has seen in a set and checks for the complement: time, extra space. Neither strictly dominates the other. Describe a situation where you would pick each, and name the general tradeoff you are navigating.
Classify by exponent, then by class. For each nest, give the exponent k for which the operation count grows like , and then its tightest big-O: (a) a single loop over n; (b) two loops nested each over n; (c) three loops nested each over n; (d) a loop that replaces n with each step until it reaches 1. One of these four has no whole-number exponent. Which, and what does that say about where sits relative to the powers of n?
Write
halvings(n)so it returns how many times you can replace n withn // 2before reaching 1: this is the hiding inside every halving loop. Then say, in one sentence, why doubling n adds only a single extra halving.The checks · run against your code
# One item is already 1, so no halving is needed. assert halvings(1) == 0 # 2 -> 1 is a single halving. assert halvings(2) == 1 # 8 -> 4 -> 2 -> 1 is three. assert halvings(8) == 3 # 1024 is 2**10, so exactly ten halvings. assert halvings(1024) == 10 # 1000 is not a power of two; integer division still lands in nine steps. assert halvings(1000) == 9 # Doubling n adds just ONE more halving. That flatness is the log. assert halvings(2000) == halvings(1000) + 1
python runs in your browser · first run downloads ~240 kbPlate VII THE HALVING COUNT · Implement halvings(n), the number of times n can be halved down to 1. Run to grade against six sizes. Doubling n adds just one step, and that flatness is . Hint one
Loop
while n > 1, and each turn setn = n // 2and bump a counter. Stop when n reaches 1; the counter holds the answer.Hint two
Each halving cuts n in half, so the number of steps is about . Doubling n just prepends one extra halving before the old sequence begins.
The solution
Halve until you hit 1, counting as you go:
def halvings(n): count = 0 while n > 1: n = n // 2 count += 1 return countThe step count grows like , so a loop shaped this way is : multiplying n by any constant adds only a constant number of steps. That is the gentlest growth above flat constant time, and it is exactly the reward binary search collects for halving its search space at every comparison.
Five errands on Fairfield Way, n students out on it. (a) Ask the first student you meet what time it is. (b) Nod once to every student you pass. (c) Have every pair of students shake hands. (d) Sort the whole Way into height order by a tournament of merges. (e) Find one student by name on a Way already sorted by name, halving the stretch you still have to search at every check. Give the growth class of each, and justify it the way we have all lecture: say what happens to the count when the crowd doubles from 1000 to 2000. Then say which two errands you could not tell apart on a linear plot of the counts, and why the log-log view separates them at a glance.
The crossover, exactly. Plan NOD covers the Way once at a flat 300 seconds plus 10 seconds a nod, so it costs . Plan SHAKE has every pair shake hands at 1 second each, so it costs . Implement both, then find the smallest n at which the quadratic plan finally loses. When the checks are green, do the harder part on paper: rerun the reasoning with a handshake that takes only a tenth of a second and show that the crossover moves to 228, not to infinity. Then say in one sentence what a tenfold improvement in a constant actually buys you.
The checks · run against your code
# A deserted Way still costs the flat 300 seconds to cover. assert nod_seconds(0) == 300 # Ten students add ten nods at ten seconds apiece. assert nod_seconds(10) == 400 # A class change: 300 + 10 * 2000. assert nod_seconds(2000) == 20300 # One student has nobody to shake hands with. assert shake_seconds(1) == 0 # Two students make exactly one pair. assert shake_seconds(2) == 1 # n(n-1)/2 pairs at a second each: about twenty-three days. assert shake_seconds(2000) == 1999000 # Doubling the crowd doubles the nodding, once the flat walk is set aside. assert nod_seconds(4000) - 300 == 2 * (nod_seconds(2000) - 300) # Doubling the crowd nearly quadruples the handshaking. That is the quadratic. assert shake_seconds(4000) > 3.9 * shake_seconds(2000) # Below the crossover the quadratic plan with the good constant genuinely wins. assert shake_seconds(37) < nod_seconds(37) # One student later it has lost, and it never wins again. assert shake_seconds(38) > nod_seconds(38) # So the crossover sits at 38. assert crossover() == 38
python runs in your browser · first run downloads ~240 kbPlate VIII THE FAIRFIELD CROSSOVER · Implement nod_seconds(n), shake_seconds(n), and crossover(). Run to grade against eleven checks. The quadratic plan with the good constant wins up to and loses forever after, which is exactly the detail big-O hides on purpose. Hint one
nod_secondsis the flat cost plus a per-student cost: 300 plus 10 for each of the n students.shake_secondscounts pairs, and you counted pairs already in the triangular nest: of them. Use integer division so the answer comes back a whole number of seconds.Hint two
For
crossover, you do not need algebra. Walk n upward from 1 and return the first n whereshake_seconds(n)is strictly greater thannod_seconds(n). It is well under a hundred, so a plain loop finds it instantly.The solution
Two closed forms and one small search:
def nod_seconds(n): return 300 + 10 * n def shake_seconds(n): return n * (n - 1) // 2 def crossover(): n = 1 while shake_seconds(n) <= nod_seconds(n): n += 1 return nAt the handshakes cost 666 seconds against the nodding’s 670, so the quadratic plan is genuinely the faster one. At it is 703 against 680, and it never leads again. At a class change, , it is about twenty-three days against a shade under six hours. Making the handshake ten times faster pushes the crossover from 38 to 228 and leaves the verdict at 2000 untouched: a better constant buys you a bigger n before you lose, never the win itself.
The costs worth knowing cold
Most day-to-day cost questions are not derivations at all, they are recall. You learn the price of the handful of operations you reach for constantly, and then reading a function’s complexity becomes little more than adding those prices up. A dictionary lookup is free, a scan of a list is linear, a sort is , a heap push pays a single climb, and a loop inside a loop over the same data is the you now know to dread. The surprises are few and worth memorising as exceptions: appending to a list is only on average, slicing costs as much as the piece you cut, and building a heap is linear even though every push into one is logarithmic.
The board below drills exactly that table. Pick a tile and it shows you an operation; choose its class from the row of five, and it tells you at once whether you were right and gives the one-line reason. Correct picks build a streak and there are no grades, so the only thing at stake is whether the price is really in your head yet. With JavaScript off the same figure is just the whole table laid out as a cheat sheet.
| Operation | Cost | Why |
|---|---|---|
| LIST | ||
list.append(x)
|
O(1) | Amortized O(1): doubling the backing block makes n appends average to a constant apiece. |
list.pop()
|
O(1) | Removing the last item shifts nothing after it, so the cost is flat. |
x in list
|
O(n) | A list has no index on its values, so membership scans every element. |
list.insert(0, x)
|
O(n) | Inserting at the front shoves every existing element up one slot. |
| DICT · SET | ||
d[k]
|
O(1) | A hash sends the key straight to its bucket, with no scan. |
x in set
|
O(1) | Set membership is that same hash lookup, not a walk down the elements. |
set(xs)
|
O(n) | Building the set hashes each of the n elements exactly once. |
sorted(s)
|
O(n log n) | Pouring a set into sorted order is still a comparison sort: n log n. |
| HEAP · SEARCH | ||
bisect(xs, v)
|
O(log n) | Binary search on a sorted list halves the range at every comparison. |
heapq.heappush(h, x)
|
O(log n) | The new item sifts up a single leaf-to-root path. |
heapq.heappop(h)
|
O(log n) | The root leaves and the last item sifts back down one path. |
heapq.heapify(xs)
|
O(n) | Bottom-up sift-down turns a raw list into a heap in linear time. |
| SORT · SCAN | ||
s[i:j]
|
O(n) | A slice copies the j minus i elements it spans, linear in the slice length. |
min(xs)
|
O(n) | Finding the smallest takes one full pass over the elements. |
sorted(xs)
|
O(n log n) | A general comparison sort needs about n log n comparisons. |
[f(a, b) for a in xs for b in xs]
|
O(n²) | Every element paired with every other: n times n work. |
The cost of every operation you reach for constantly, in one table. Enable JavaScript to turn it into a quiz: pick a tile, guess the class, and build a streak.