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.
Least you need to know
- A loop that performs constant work
ntimes isΘ(n). - Two nested loops over ranges of size
noften lead toΘ(n^2)work. - A triangular nested loop with counts
1+2+⋯+nis 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
Worked example
- A single pass over an array of length
nwith constant work per element usesΘ(n)time. - A nested pass over every ordered pair of elements uses about
n^2body executions. - A doubling loop reaches
nafter aboutlog_2 nupdates.
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 it
- 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.