Complexity: how work grows
Estimate order of growth by counting dominant operations in loops, searches, and elementary sorts.
After this lesson
You should be able to
- Classify simple code as constant, logarithmic, linear, or quadratic growth.
- Separate growth rate from exact running time.
Ask what changes when n doubles
Complexity describes how resource use grows with input size. One array access is constant O(1). Scanning every element is linear O(n). Repeatedly halving the candidate set is logarithmic O(log n). Comparing many pairs in nested loops is often quadratic O(n²).
Big-O suppresses constant factors and lower-order terms to focus on long-run growth. 3n + 20 is O(n); n² + n is O(n²). This does not mean constants never matter in real programs.
Connect the code to the count
Linear search makes at most n target comparisons. Binary search makes about log₂n comparisons but requires sorted data. An ordinary selection sort makes roughly n(n−1)/2 comparisons, so its growth is quadratic.
Measure the operation that represents the algorithm's work, not every punctuation mark. Then identify how many times it runs as n grows. State best, average, or worst case when the distinction changes the answer.
for (size_t i = 0; i < n; i++) {
for (size_t j = i + 1; j < n; j++) {
compare(values[i], values[j]);
}
}Try it yourself
Classify a loop that starts at n and repeatedly divides its counter by 2.
Need a hint?
How many halvings reduce n to 1?
Check the worked solution
It is O(log n), because each iteration halves the remaining magnitude.
Quick check
If input size doubles, which growth roughly quadruples?
Why this lesson exists
Syllabus mapping
Introductory order-of-complexity concepts through example programs
Maps to course outcomes CO1, CO6.