Thinking about efficiency

Ideas to remember

1. 01Big-O describes the shape of growth: as the input n grows, how does the amount of work grow with it?
2. 02O(1) does not grow with n, O(n) doubles when the data doubles, O(n²) quadruples when the data doubles.
3. 03Count the nested loops over the data: no loop is often O(1), one loop is usually O(n), a loop inside a loop is usually O(n²).
4. 04Choosing the right data structure can change the shape of growth: a set turns an n² duplicate check or guest-list scan into n work.
5. 05Trading a little memory for a lower shape of growth is a bargain you will make again and again.
6. 06Selection sort is O(n²) and the built-in sorted is O(n log n): learn selection sort to understand sorting, use sorted to actually sort.

Words

n

The input size; you count the steps as a function of it instead of timing the program with a stopwatch.

O(1), O(n), O(n²)

Constant, linear, quadratic: the three shapes of growth a beginner meets most.

if one in seen:

A membership check on a set is roughly O(1), so the whole duplicate check becomes O(n) in one pass.

sorted(scores, reverse=True)

Returns a new sorted list, flipped when reverse=True, and leaves the original untouched.

scores.sort()

Does the same job as sorted but rearranges the original list in place.

sorted(words, key=len)

Sorts by whatever you choose, here the length of each word.