Loops
Repeat work while a condition holds or for each item in a collection. The source of both power and infinite loops.
Level: beginner
What is it?
A loop repeats a block. A for loop walks a known sequence or a counted range; a while loop runs until a condition turns false. break exits early and continue skips to the next pass. A loop is correct when it has an invariant — something true before every pass — and a variable that moves toward the stopping condition.
Why does it matter?
Loops turn a fixed program into one whose running time depends on the input, which is where cost analysis begins: one loop over n items is O(n), a loop inside a loop is O(n²). Off-by-one and non-terminating loops are among the most common defects.
Mental model
Walking down a hallway of doors. A for loop says 'open every door once, in order.' A while loop says 'keep walking until the alarm stops.'
How it works
- for x in items: use it when you have a collection or a known count, so there is no manual index to get wrong.
- while condition: use it when the number of passes depends on something computed inside the loop.
- Invariant plus progress: state what stays true on every pass and what changes so the loop must end.
- Off-by-one errors live at the boundaries: range(n) covers 0 to n-1, and slices exclude their end.
- Nested loops multiply: a loop over n inside a loop over n is n² work.
- Modifying a collection while iterating over it skips or repeats elements. Iterate over a copy or build a new list.
Steps
- Set up the state
- Test the condition
- Run the body
- Update toward the end
- Repeat or exit
Code example: An invariant and steady progress
def total(nums):
s = 0 # invariant: s == sum of the numbers seen so far
for x in nums:
s += x
return s
i = 10
while i > 0: # progress: i shrinks by 3 on every pass
i -= 3
print(total([1, 2, 3]), i) # 6 -2Complexity and trade-offs
Time: One pass over n items is O(n); two nested passes are O(n²)
Space: O(1) extra for a simple accumulator
Trade-offs
- Simple loops are the cheapest way to touch every element once
- Nested loops are the first thing to look at when a program is slow on large input
Real-world usage
- Processing every record in a file or table
- Retrying an operation until it succeeds or a limit is reached
- Game loops, event loops, and server accept loops
Common mistakes
- Using <= where < was meant and reading one element past the end.
- A while loop whose condition variable is never updated.
- Removing items from a list while looping over it.
Interview questions
How do you show a loop is correct?
State a loop invariant, show it holds before the first pass and is preserved by each pass, and show that the invariant plus the exit condition imply the result. Then show some quantity decreases so the loop terminates.
When would you choose while over for?
When you do not know in advance how many passes you need — reading until end of input, retrying until success, or converging on a value. A for loop fits a known collection or count.
What does a nested loop cost?
The passes multiply. Two loops over n items do about n² comparisons, which is fine at n = 1,000 and painful at n = 1,000,000. Often a hash set or a sort removes the inner loop.