Stage 1 · Lesson 2 of 6
Counting operations in loops
Most complexity questions are answered by . Two loops one after the other add their costs. A loop inside another loop multiplies them.
A loop that doubles or halves its counter each time runs about log n times, because that is how many halvings it takes to get from n down to 1. When inputs have different sizes, give each its own letter: a loop over n inside a loop over m is O(n × m), not O(n²).
Common traphidden work: every call inside a loop has its own cost. Slicing a list, searching it with indexOf or in, removing the first item of an array, and building a by adding to it again and again are all O(n). So one innocent-looking line can turn a loop of n steps into n² steps.
A question to check yourself, an AI practice session and 1 cheat sheet entry come with the full roadmap. Unlock
Resources for this stage
Start with· follow one of these
- CoursePaidGrokking Algorithm Complexity and Big-O
Design Gurus · Beginner · Subscription
Short course on exactly this stage, including the amortised and space cases people miss
- CourseFreeMIT 6.006 Introduction to Algorithms
MIT OpenCourseWare · Intermediate
Free: lecture 1 and recitation 1 on asymptotic notation and the model of computation
Keep handy
Also worth your time
Time and space complexity worked through five common algorithms