Algorithms / Loop Analysis
Least You Need to Know: Analyzing Loops and Nested Loops
For loop analysis, count how many times the body executes and multiply by the work per execution. Nested loops often multiply counts, while doubling or halving patterns often lead to logarithms.
The least you need to know
- A loop that performs constant work `n` times is `Θ(n)`.
- Two nested loops over ranges of size `n` often lead to `Θ(n^2)` work.
- A triangular nested loop with counts `1+2+⋯+n` is still `Θ(n^2)`.
- When a loop variable doubles or halves each time, the number of iterations is often `Θ(log n)`.
- Time complexity and extra space complexity are separate questions.
Key notation
for i in range(n)
about n iterations
∑_{i=1}^n i
triangular count
i ← 2i
doubling step
Tiny worked example
- A single pass over an array of length `n` with constant work per element uses `Θ(n)` time.
- A nested pass over every ordered pair of elements uses about `n^2` body executions.
- A doubling loop reaches `n` after about `log_2 n` updates.
Common mistakes
- Students often count the number of loops instead of the number of body executions.
- Students often forget that triangular sums are still quadratic.
- Students often mix up time cost with extra space cost.
How to recognize this kind of problem
- Write down how many times the innermost body runs.
- If one loop is fully inside another, multiply the iteration counts.
- If a variable doubles each step, ask how many doublings reach `n`.
Next recommended lesson
Continue through this topic with Least You Need to Know: Modular Arithmetic, Divisibility, and Hashing Intuition.
Least You Need to Know: Modular Arithmetic, Divisibility, and Hashing IntuitionRelated lessons
Keep going with nearby lessons in the same topic.