Counted Iteration (for)
Description
A for loop is a control flow statement that allows you to repeat a block of code a specific, predetermined number of times. It is called counted iteration because you know in advance exactly how many times the loop will execute before it starts.
The for loop is the most commonly used loop in programming. It bundles three essential pieces into a single, compact line:
- Initialization — Set up a counter variable (e.g.,
i = 0) - Condition — Define when the loop should stop (e.g.,
i < 5) - Update — Change the counter after each iteration (e.g.,
i++)
For loops are ideal when:
- You need to traverse an array from start to end (or end to start)
- You want to repeat an action a known number of times
- You need to iterate over a range of numbers
- You are processing elements of a collection one by one
Understanding the for loop is fundamental because it is the building block for nearly every algorithm — from simple array traversal to complex nested operations like brute-force search, matrix manipulation, and dynamic programming table filling.
Examples
Example 1 — Print Numbers 0 to 4
Code (C++/Java style):
for (int i = 0; i < 5; i++) {
print(i);
}
Output: 0 1 2 3 4
Explanation:
- Initialization:
istarts at 0 - Iteration 1: Is
i < 5? Yes (0 < 5). Print 0. Incrementito 1. - Iteration 2: Is
i < 5? Yes (1 < 5). Print 1. Incrementito 2. - Iteration 3: Is
i < 5? Yes (2 < 5). Print 2. Incrementito 3. - Iteration 4: Is
i < 5? Yes (3 < 5). Print 3. Incrementito 4. - Iteration 5: Is
i < 5? Yes (4 < 5). Print 4. Incrementito 5. - Termination: Is
i < 5? No (5 < 5 is false). Loop ends.
The loop ran exactly 5 times, printing values 0 through 4.
Example 2 — Sum of Array Elements
Input: arr = [3, 7, 2, 8, 5]
Code:
sum = 0
for (int i = 0; i < 5; i++) {
sum = sum + arr[i];
}
Output: sum = 25
Explanation:
- Start with
sum = 0 - i=0: sum = 0 + arr[0] = 0 + 3 = 3
- i=1: sum = 3 + arr[1] = 3 + 7 = 10
- i=2: sum = 10 + arr[2] = 10 + 2 = 12
- i=3: sum = 12 + arr[3] = 12 + 8 = 20
- i=4: sum = 20 + arr[4] = 20 + 5 = 25
The for loop visits each element exactly once, accumulating the total. This is O(n) — one of the most fundamental patterns in programming.
Example 3 — Reverse Traversal
Input: arr = [10, 20, 30, 40, 50]
Code:
for (int i = 4; i >= 0; i--) {
print(arr[i]);
}
Output: 50 40 30 20 10
Explanation:
- Initialization:
istarts at 4 (the last index) - The condition is
i >= 0(continue while index is valid) - The update is
i--(decrement by 1 each time) - We traverse the array from right to left
This demonstrates that for loops are not limited to counting upward — you can go backward, skip elements (i += 2), or use any update expression.
Example 4 — Nested For Loop (Multiplication Table)
Code:
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
print(i * j);
}
}
Output: 1 2 3 2 4 6 3 6 9
Explanation:
- The outer loop runs 3 times (i = 1, 2, 3)
- For EACH value of i, the inner loop runs 3 times (j = 1, 2, 3)
- Total iterations: 3 × 3 = 9
- This is O(n²) — nested loops multiply the iteration counts. Understanding this is crucial for analyzing algorithm complexity.
Constraints
This is a conceptual topic about loop constructs. General constraints to keep in mind:
- The loop counter variable must be properly initialized before the first check
- The condition must eventually become false, otherwise the loop runs forever (infinite loop)
- The update step must move the counter toward the termination condition
- Nested for loops multiply execution counts: a loop of n inside a loop of m gives n × m total iterations
- In C++/Java, the loop variable declared inside
for(int i = ...)is scoped to the loop body - In Python,
for i in range(n)generates values 0, 1, ..., n-1 (n is excluded) - Array index-based loops must ensure the index stays within bounds: 0 ≤ i < array_length
Editorial
Anatomy of a For Loop
Intuition
Think of a for loop like a coach making athletes run laps around a track. Before the first lap, the coach says: "Start at lap zero." Before every lap, the coach checks: "Have you run fewer than 5 laps?" If yes, the athlete runs the lap and the coach increments the lap counter. When the counter hits 5, the coach says "Stop."
The for loop has three components:
for (initialization; condition; update) {
body;
}
Execution order (CRITICAL — most beginners get this wrong):
- Initialization runs ONCE, before anything else
- Condition is checked BEFORE each iteration (including the first)
- Body executes only if condition is true
- Update runs AFTER the body completes
- Go back to step 2
This means:
- If the condition is false from the start, the body executes ZERO times
- The update runs AFTER the body, not before it
- After the last iteration, the update runs, THEN the condition fails, and the loop exits
In Python, the for loop works differently — it iterates over an iterable (like range(), a list, or a string) rather than using an explicit condition and update:
for i in range(5): # i takes values 0, 1, 2, 3, 4
print(i)
Python's range(start, stop, step) generates a sequence of numbers. The loop variable automatically takes the next value from this sequence on each iteration. This is conceptually equivalent to C/Java's for (int i = start; i < stop; i += step).
Step-by-Step Explanation
Let's trace a for loop that computes the sum of arr = [3, 7, 2, 8, 5]:
sum = 0
for (int i = 0; i < 5; i++) {
sum = sum + arr[i];
}
Step 1: Initialize sum = 0. Then execute the for loop: set i = 0 (initialization runs once).
Step 2: Check condition: i < 5? → 0 < 5? → YES. Enter the body.
Step 3: Execute body: sum = sum + arr[0] → sum = 0 + 3 = 3.
Step 4: Execute update: i++ → i = 1.
Step 5: Check condition: i < 5? → 1 < 5? → YES. Enter the body.
Step 6: Execute body: sum = sum + arr[1] → sum = 3 + 7 = 10.
Step 7: Execute update: i++ → i = 2.
Step 8: Check condition: 2 < 5? → YES. Body: sum = 10 + 2 = 12. Update: i = 3.
Step 9: Check condition: 3 < 5? → YES. Body: sum = 12 + 8 = 20. Update: i = 4.
Step 10: Check condition: 4 < 5? → YES. Body: sum = 20 + 5 = 25. Update: i = 5.
Step 11: Check condition: 5 < 5? → NO. Loop terminates. Final sum = 25.
For Loop — Computing Array Sum — Watch how the for loop visits each array element exactly once, accumulating a running sum. The loop counter i moves left to right through the array.
Algorithm
For Loop Execution Algorithm:
- Execute the initialization statement (runs exactly once)
- Evaluate the condition:
- If
true→ go to step 3 - If
false→ exit the loop (go to step 5)
- If
- Execute the body (the code block inside the loop)
- Execute the update statement, then go back to step 2
- Continue with the code after the loop
Key observations:
- The initialization runs exactly once
- The condition is checked n + 1 times (n times it's true, 1 final time it's false)
- The body runs exactly n times
- The update runs exactly n times (after each body execution)
- After the loop, the counter variable holds the value that caused the condition to fail
Code
#include <iostream>
using namespace std;
int main() {
// === Basic for loop: print 0 to 4 ===
cout << "Basic loop: ";
for (int i = 0; i < 5; i++) {
cout << i << " ";
}
cout << endl; // Output: 0 1 2 3 4
// === Sum of array elements ===
int arr[] = {3, 7, 2, 8, 5};
int n = 5;
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}
cout << "Sum: " << sum << endl; // Output: 25
// === Reverse traversal ===
cout << "Reversed: ";
for (int i = n - 1; i >= 0; i--) {
cout << arr[i] << " ";
}
cout << endl; // Output: 5 8 2 7 3
// === Step by 2 (every other element) ===
cout << "Every other: ";
for (int i = 0; i < n; i += 2) {
cout << arr[i] << " ";
}
cout << endl; // Output: 3 2 5
// === Range-based for loop (C++11) ===
cout << "Range-based: ";
for (int val : arr) {
cout << val << " ";
}
cout << endl; // Output: 3 7 2 8 5
return 0;
}# === Basic for loop: print 0 to 4 ===
print("Basic loop:", end=" ")
for i in range(5): # range(5) generates 0, 1, 2, 3, 4
print(i, end=" ")
print() # Output: 0 1 2 3 4
# === Sum of array elements ===
arr = [3, 7, 2, 8, 5]
total = 0
for i in range(len(arr)):
total += arr[i]
print(f"Sum: {total}") # Output: 25
# === Pythonic: iterate over values directly ===
total2 = 0
for val in arr: # No index needed!
total2 += val
print(f"Sum (pythonic): {total2}") # Output: 25
# === Reverse traversal ===
print("Reversed:", end=" ")
for i in range(len(arr) - 1, -1, -1): # range(4, -1, -1) → 4, 3, 2, 1, 0
print(arr[i], end=" ")
print() # Output: 5 8 2 7 3
# === Step by 2 ===
print("Every other:", end=" ")
for i in range(0, len(arr), 2): # range(start, stop, step)
print(arr[i], end=" ")
print() # Output: 3 2 5
# === enumerate: index + value together ===
for i, val in enumerate(arr):
print(f"arr[{i}] = {val}")public class ForLoopDemo {
public static void main(String[] args) {
// === Basic for loop: print 0 to 4 ===
System.out.print("Basic loop: ");
for (int i = 0; i < 5; i++) {
System.out.print(i + " ");
}
System.out.println(); // Output: 0 1 2 3 4
// === Sum of array elements ===
int[] arr = {3, 7, 2, 8, 5};
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
}
System.out.println("Sum: " + sum); // Output: 25
// === Reverse traversal ===
System.out.print("Reversed: ");
for (int i = arr.length - 1; i >= 0; i--) {
System.out.print(arr[i] + " ");
}
System.out.println(); // Output: 5 8 2 7 3
// === Step by 2 ===
System.out.print("Every other: ");
for (int i = 0; i < arr.length; i += 2) {
System.out.print(arr[i] + " ");
}
System.out.println(); // Output: 3 2 5
// === Enhanced for loop (for-each) ===
System.out.print("For-each: ");
for (int val : arr) {
System.out.print(val + " ");
}
System.out.println(); // Output: 3 7 2 8 5
}
}Complexity Analysis
Time Complexity of a Single For Loop: O(n)
A for loop that runs from i = 0 to i < n executes the body exactly n times. If each iteration does O(1) work (like accessing an array element, adding two numbers, or comparing values), the total time is n × O(1) = O(n).
Space Complexity: O(1)
A basic for loop uses only a counter variable i and possibly a few accumulator variables (like sum). These do not grow with the input size.
Why this matters: Almost every algorithm starts with a for loop. Understanding that a single loop over n elements costs O(n) is the foundation for all complexity analysis. When you later encounter nested loops (O(n²)), you will understand why — it is simply n repetitions of an O(n) loop.
Nested For Loops and Their Cost
Intuition
A nested for loop is a for loop inside another for loop. Think of it as a clock: the minute hand (inner loop) completes a full rotation for every single tick of the hour hand (outer loop). If the hour hand ticks 12 times and the minute hand goes around 60 times per tick, the total number of minute ticks is 12 × 60 = 720.
Similarly, if the outer loop runs n times and the inner loop runs m times for each outer iteration, the total number of inner-body executions is n × m. When n = m, this gives O(n²) — quadratic time.
Nested loops are the source of most brute-force algorithms:
- Checking all pairs in an array → O(n²)
- Multiplying matrices → O(n³)
- Generating all substrings → O(n²)
Recognizing nested loops and their costs is essential for understanding why brute-force solutions are slow and why optimized algorithms (using hash maps, sorting, or two pointers) are needed.
Step-by-Step Explanation
Let's trace a nested for loop that finds all pairs in arr = [3, 7, 2]:
for (int i = 0; i < 3; i++) {
for (int j = i + 1; j < 3; j++) {
print(arr[i], arr[j]);
}
}
Step 1: Outer loop starts: i = 0. Inner loop starts: j = 1.
Step 2: Inner body: print pair (arr[0], arr[1]) = (3, 7). Inner update: j = 2.
Step 3: Inner body: print pair (arr[0], arr[2]) = (3, 2). Inner update: j = 3.
Step 4: Inner condition 3 < 3 is false. Inner loop ends for i = 0.
Step 5: Outer update: i = 1. Inner loop restarts: j = 2.
Step 6: Inner body: print pair (arr[1], arr[2]) = (7, 2). Inner update: j = 3.
Step 7: Inner condition 3 < 3 is false. Inner loop ends for i = 1.
Step 8: Outer update: i = 2. Inner loop starts: j = 3. Condition 3 < 3 is false immediately — inner loop does not execute.
Step 9: Outer condition: 3 < 3 is false. Outer loop ends. Total pairs printed: 3.
Nested For Loop — Finding All Pairs — Watch how the outer loop fixes one element while the inner loop scans through the remaining elements, generating every unique pair. The total iterations are n×(n-1)/2.
Algorithm
Nested For Loop — All Pairs Generation:
- Set outer loop counter
i = 0 - While
i < n:
a. Set inner loop counterj = i + 1
b. Whilej < n:- Process pair
(arr[i], arr[j]) - Increment
j
c. Incrementi
- Process pair
- Total pairs processed: n × (n-1) / 2
Why j = i + 1? Starting the inner loop at i + 1 instead of 0 avoids:
- Pairing an element with itself (i == j)
- Duplicate pairs: (3,7) and (7,3) represent the same pair, so we only generate one
Code
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> arr = {3, 7, 2, 8, 5};
int n = arr.size();
// === Generate all pairs ===
cout << "All pairs:" << endl;
int pairCount = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
cout << "(" << arr[i] << ", " << arr[j] << ")" << endl;
pairCount++;
}
}
cout << "Total pairs: " << pairCount << endl;
// n*(n-1)/2 = 5*4/2 = 10 pairs
// === Nested loop: Multiplication table ===
cout << "\nMultiplication Table (3x3):" << endl;
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
cout << i * j << "\t";
}
cout << endl;
}
return 0;
}arr = [3, 7, 2, 8, 5]
n = len(arr)
# === Generate all pairs ===
print("All pairs:")
pair_count = 0
for i in range(n):
for j in range(i + 1, n):
print(f"({arr[i]}, {arr[j]})")
pair_count += 1
print(f"Total pairs: {pair_count}")
# n*(n-1)/2 = 5*4/2 = 10 pairs
# === Nested loop: Multiplication table ===
print("\nMultiplication Table (3x3):")
for i in range(1, 4):
for j in range(1, 4):
print(f"{i*j}\t", end="")
print()
# === Common pattern: 2D grid traversal ===
grid = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
print("\nGrid traversal:")
for row in range(len(grid)):
for col in range(len(grid[0])):
print(f"grid[{row}][{col}] = {grid[row][col]}")public class NestedForLoop {
public static void main(String[] args) {
int[] arr = {3, 7, 2, 8, 5};
int n = arr.length;
// === Generate all pairs ===
System.out.println("All pairs:");
int pairCount = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
System.out.println("(" + arr[i] + ", " + arr[j] + ")");
pairCount++;
}
}
System.out.println("Total pairs: " + pairCount);
// n*(n-1)/2 = 5*4/2 = 10 pairs
// === Nested loop: Multiplication table ===
System.out.println("\nMultiplication Table (3x3):");
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
System.out.print(i * j + "\t");
}
System.out.println();
}
// === 2D array traversal ===
int[][] grid = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
System.out.println("\nGrid traversal:");
for (int row = 0; row < grid.length; row++) {
for (int col = 0; col < grid[0].length; col++) {
System.out.println("grid[" + row + "][" + col + "] = " + grid[row][col]);
}
}
}
}Complexity Analysis
Time Complexity of Nested For Loops: O(n²)
The outer loop runs n times. For each outer iteration, the inner loop runs up to n-1 times. The total number of inner body executions is:
(n-1) + (n-2) + (n-3) + ... + 1 + 0 = n×(n-1)/2
This simplifies to O(n²). For an array of 10,000 elements, that is approximately 50 million operations.
Space Complexity: O(1)
Only two counter variables (i and j) and possibly an accumulator. No additional data structures that grow with input.
Complexity hierarchy of loop nesting:
| Loop Structure | Time Complexity | Example |
|---|---|---|
| Single loop | O(n) | Sum of array |
| Two nested loops | O(n²) | All pairs, bubble sort |
| Three nested loops | O(n³) | Matrix multiplication, all triples |
| k nested loops | O(nᵏ) | Rarely practical for k > 3 |
This is why algorithm optimization matters: reducing from O(n²) to O(n log n) or O(n) using smart data structures (hash maps, sorted arrays, heaps) is the core skill in competitive programming and software engineering.
Common For Loop Patterns
Intuition
Beyond basic counting and pair generation, for loops appear in several standard patterns that you will encounter repeatedly in programming and algorithm design:
1. Accumulation Pattern: Build up a result by processing each element.
result = initial_value
for each element:
result = combine(result, element)
Examples: sum, product, maximum, minimum, concatenation.
2. Search Pattern: Find an element that satisfies a condition.
for each element:
if condition(element):
return element
return not_found
Examples: linear search, find first negative, find duplicate.
3. Filter Pattern: Collect elements meeting a criterion.
result = []
for each element:
if condition(element):
result.add(element)
Examples: get all even numbers, filter strings longer than 5.
4. Transform Pattern: Create a new collection by modifying each element.
result = []
for each element:
result.add(transform(element))
Examples: square each number, convert to uppercase, compute prefix sums.
5. Counting Pattern: Count elements satisfying a condition.
count = 0
for each element:
if condition(element):
count++
Examples: count positives, count vowels, count occurrences.
Every algorithm you will learn builds upon one or more of these fundamental loop patterns.
Step-by-Step Explanation
Let's demonstrate the Search Pattern — finding the maximum element in arr = [3, 7, 2, 8, 5]:
Step 1: Initialize max_val = arr[0] = 3. This is our best candidate so far.
Step 2: i=1: Compare arr[1]=7 with max_val=3. Since 7 > 3, update max_val = 7.
Step 3: i=2: Compare arr[2]=2 with max_val=7. Since 2 < 7, no update. Max stays 7.
Step 4: i=3: Compare arr[3]=8 with max_val=7. Since 8 > 7, update max_val = 8.
Step 5: i=4: Compare arr[4]=5 with max_val=8. Since 5 < 8, no update. Max stays 8.
Step 6: Loop ends. Return max_val = 8.
This is O(n) — we made exactly 4 comparisons (n-1) to find the maximum. No nested loops needed.
Algorithm
Five Fundamental For Loop Patterns:
- Accumulate: Initialize result → loop through elements → combine each with result → return result
- Search: Loop through elements → check condition → return first match (or not_found)
- Filter: Initialize empty collection → loop → add elements meeting condition → return collection
- Transform: Initialize empty collection → loop → add transformed version of each element → return collection
- Count: Initialize counter = 0 → loop → increment counter when condition is met → return counter
These five patterns, alone and in combination, account for the vast majority of for loop usage in real-world programming and competitive coding.
Code
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
vector<int> arr = {3, 7, 2, 8, 5};
int n = arr.size();
// Pattern 1: ACCUMULATE — find sum
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}
cout << "Sum: " << sum << endl; // 25
// Pattern 2: SEARCH — find maximum
int maxVal = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > maxVal) {
maxVal = arr[i];
}
}
cout << "Max: " << maxVal << endl; // 8
// Pattern 3: FILTER — collect even numbers
vector<int> evens;
for (int i = 0; i < n; i++) {
if (arr[i] % 2 == 0) {
evens.push_back(arr[i]);
}
}
cout << "Evens: ";
for (int e : evens) cout << e << " "; // 2 8
cout << endl;
// Pattern 4: TRANSFORM — square each element
vector<int> squared;
for (int i = 0; i < n; i++) {
squared.push_back(arr[i] * arr[i]);
}
cout << "Squared: ";
for (int s : squared) cout << s << " "; // 9 49 4 64 25
cout << endl;
// Pattern 5: COUNT — count elements > 4
int count = 0;
for (int i = 0; i < n; i++) {
if (arr[i] > 4) {
count++;
}
}
cout << "Elements > 4: " << count << endl; // 3
return 0;
}arr = [3, 7, 2, 8, 5]
# Pattern 1: ACCUMULATE — find sum
total = 0
for val in arr:
total += val
print(f"Sum: {total}") # 25
# Pythonic: sum(arr)
# Pattern 2: SEARCH — find maximum
max_val = arr[0]
for val in arr[1:]:
if val > max_val:
max_val = val
print(f"Max: {max_val}") # 8
# Pythonic: max(arr)
# Pattern 3: FILTER — collect even numbers
evens = []
for val in arr:
if val % 2 == 0:
evens.append(val)
print(f"Evens: {evens}") # [2, 8]
# Pythonic: [x for x in arr if x % 2 == 0]
# Pattern 4: TRANSFORM — square each element
squared = []
for val in arr:
squared.append(val * val)
print(f"Squared: {squared}") # [9, 49, 4, 64, 25]
# Pythonic: [x*x for x in arr]
# Pattern 5: COUNT — count elements > 4
count = 0
for val in arr:
if val > 4:
count += 1
print(f"Elements > 4: {count}") # 3
# Pythonic: sum(1 for x in arr if x > 4)import java.util.ArrayList;
import java.util.List;
public class LoopPatterns {
public static void main(String[] args) {
int[] arr = {3, 7, 2, 8, 5};
// Pattern 1: ACCUMULATE — find sum
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
}
System.out.println("Sum: " + sum); // 25
// Pattern 2: SEARCH — find maximum
int maxVal = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > maxVal) {
maxVal = arr[i];
}
}
System.out.println("Max: " + maxVal); // 8
// Pattern 3: FILTER — collect even numbers
List<Integer> evens = new ArrayList<>();
for (int val : arr) {
if (val % 2 == 0) {
evens.add(val);
}
}
System.out.println("Evens: " + evens); // [2, 8]
// Pattern 4: TRANSFORM — square each element
int[] squared = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
squared[i] = arr[i] * arr[i];
}
System.out.print("Squared: ");
for (int s : squared) System.out.print(s + " "); // 9 49 4 64 25
System.out.println();
// Pattern 5: COUNT — count elements > 4
int count = 0;
for (int val : arr) {
if (val > 4) {
count++;
}
}
System.out.println("Elements > 4: " + count); // 3
}
}Complexity Analysis
All five patterns share the same complexity:
Time Complexity: O(n)
Each pattern uses a single for loop that visits every element exactly once. The work done per element (comparison, addition, check, append) is O(1). Total: n × O(1) = O(n).
Space Complexity:
- Accumulate: O(1) — only a running total
- Search: O(1) — only the current best
- Filter: O(k) where k ≤ n — the filtered subset
- Transform: O(n) — a new array of the same size
- Count: O(1) — only a counter
Summary of For Loop Complexities:
| Pattern | Loops | Time | Space |
|---|---|---|---|
| Single traversal | 1 | O(n) | O(1) |
| All pairs | 2 nested | O(n²) | O(1) |
| All triples | 3 nested | O(n³) | O(1) |
| Traverse 2D grid (m×n) | 2 nested | O(m×n) | O(1) |
| Binary search style | 1 (halving) | O(log n) | O(1) |
The for loop is the most fundamental building block of algorithm complexity. Mastering it means understanding exactly how many operations your code performs — which is the essence of Big-O analysis.