Analyzing Simple Loops
What you'll learn: How to count operations inside a single loop and express the total runtime as a formula based on input size.
The Core Idea
When a loop runs, it repeats a block of operations multiple times. To analyze its runtime, you count how many operations happen in one iteration, then multiply by the number of iterations.
For a simple loop that runs n times (where n is your input size), if each iteration performs c constant operations, the total operation count is:
Total operations = c × n
This gives you a runtime formula that describes how the loop's cost grows with input size.
Walking Through an Example
Imagine a loop that prints each element of an array:
for i from 0 to n-1:
print array[i]
Step 1: Count operations per iteration:
- Access
array[i]: 1 operation - Print: 1 operation
- Loop overhead (increment, compare): ~2 operations
Total per iteration: ~4 operations
Step 2: Count iterations:
- The loop runs exactly
ntimes (once per array element)
Step 3: Multiply:
- Total operations = 4 × n
The runtime grows linearly with n. Double the array size, double the operations.
Why This Matters
This formula lets you predict performance. An array of 1,000 elements? Expect ~4,000 operations. This systematic counting is the foundation of understanding how efficient your code is.
Key Takeaway: To analyze a simple loop, count the operations per iteration, multiply by the number of iterations, and derive a runtime formula in terms of input size n.