Performance: O-notation
This course covers O-notation as a decision tool for Rails code. It explains what the notation claims and what it discards: constants, lower-order terms and the machine. It walks through five growth curves using concrete pairs, such as a query per record against one query. Later lessons cover the accidental quadratic from include? on an array, space complexity, and average, amortized and worst case. The course closes with the point where two curves cross and with when the analysis is worth doing.
What you'll learn
- ✓What O-notation claims and what it leaves out
- ✓The five growth curves common in Rails code
- ✓Finding and fixing include? inside a loop with Set or index_by
- ✓Space complexity and the memory cost of Active Record objects
- ✓The difference between average, amortized and worst case
- ✓Computing where two curves cross and deciding which side your data is on
What O-notation is for, and what it hides
A code review comment says "this is O(n squared), rewrite it". The loop runs over a user's enrolled courses. The whole catalogue is a few hundred courses, and a learner is typically enrolled in a handful. The rewrite would save microseconds and cost a reviewer an afternoon.
Read the full lesson free →Curriculum
7 lessonsWhat O-notation is for, and what it hides
Explains what O-notation claims, the constants, terms and machine it discards, and why knowing n comes first.
The curves a Rails engineer meets
Walks through five common curves using pairs like per-record queries, index lookups, where to sort and batching.
The accidental quadratic: `include?` inside a loop
Shows how include? on an array inside a loop becomes quadratic, measures the cost, and fixes it with Set.
Space complexity: the curve that pages you
Treats peak memory as a separate curve, covering Active Record object cost, pluck and unbounded lookup tables.
Amortized, average, and worst case
Separates average, amortized and worst case, using Array#push, Hash collisions, hash flooding and quicksort as examples.
The threshold question: where the curves cross
Computes where two curves cross and applies it to a 50-level scan and the leaderboard refresh job.
When the analysis is worth doing
Gives a four-condition filter for deciding which loops deserve analysis and recaps the earlier lessons.