v[i] // 3 operations, always
v.push_back(it) // 5 operations if there's room
// ~3n + 5 if it must grow
list.push_front(it) // 4 operations, always
Counting exact operations is honest but useless for comparing algorithms, the number depends on the compiler, the machine, the mood of the cache. What we actually care about is how the cost changes as n grows.
Two Things We Don't Care About
Constant factors
3n + 5
100n + 2000
Both grow proportionally to n. Double n, double the work.
Lower-order terms
n² + 50n + 700
At n = 1000, the n² term is 20× everything else combined.
So we throw both away and keep only the term that dominates. What's left is the order of growth.
Big-Oh Notation
We write O( f(n) ): "on the order of f of n".
Exact count
Big-Oh
Name
3
O(1)
constant
log₂ n + 4
O(lg n)
logarithmic
3n + 5
O(n)
linear
2n lg n + n
O(n lg n)
linearithmic
n² + 50n + 700
O(n²)
quadratic
2ⁿ
O(2ⁿ)
exponential
Big-Oh is an upper bound on the shape of the growth, not a promise about seconds.
The Curves That Matter
Near the origin the differences look academic. That is exactly why they surprise people in production, the gap only opens up once the data gets big.
Talk to your neighbor · TTYN
An algorithm takes 4n + 200 steps. Its complexity is…
A. O(4n)
B. O(n)
C. O(n + 200)
D. O(200)
✓ Answer
B. O(n). Constant multipliers and added constants both drop out. 4n + 200, n, and 1000n + 5 are all O(n): double the input, roughly double the work.
Reading It Off the Code
for (int i = 0; i < n; ++i) {
total += a[i];
}
One loop over n → O(n)
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (a[i] == a[j]) ...
}
}
Loop inside a loop → O(n²)
Rule of thumb: loops in sequence add (keep the biggest), loops nested multiply. Halving the problem each pass gives you a lg n.
Talk to your neighbor · TTYN
What is the complexity of this loop?
for (int i = 1; i < n; i = i * 2) {
cout << i << endl;
}
A. O(n)
B. O(n²)
C. O(lg n)
D. O(n lg n)
✓ Answer
C. O(lg n).i doubles every pass, so it reaches n after about log₂ n steps. Any loop that multiplies or divides its counter is logarithmic: this is why binary search is so fast.
What We've Built So Far
Operation
Dynamic array
Linked list
index v[i]
O(1)
O(n)
append
O(1) amortized
O(1)
prepend
O(n)
O(1)
insert / remove at position
O(n)
O(n)
search (unsorted)
O(n)
O(n)
traverse everything
O(n)
O(n)
The same table you filled in by counting, now in the language everyone uses.
Why This Matters: Searching
One million items, and you need to find one.
Approach
Complexity
Comparisons
Linear search
O(n)
up to 1,000,000
Binary search (sorted)
O(lg n)
about 20
Fifty thousand times less work, from the same data, just organized differently. That is the entire argument for this course.
Demo
Timing O(n) against O(n²) on real data.
(same laptop, same data, wildly different patience)
Talk to your neighbor · TTYN
Algorithm A is O(n²), algorithm B is O(n lg n). Which should you use?
A. Always B; it has the better complexity
B. Always A, simpler code runs faster
C. B for large n; for small n, A may well be faster
D. Whichever is easier to write
✓ Answer
C. Big-Oh describes behavior as n grows. For small inputs the constants that we dropped can dominate: which is why real sort libraries switch to insertion sort for tiny sub-arrays. Know the asymptotics, then measure.
Overloading << for Your Container
// in List.h
ostream& operator<<(ostream &out, const List &list);
// in List.cpp
ostream& operator<<(ostream &out, const List &list) {
list.writeTo(out);
return out;
}
Week 3's rule again: a free function, taking the stream on the left, returning the stream so it chains. Traversing the whole list to print it is O(n), as you'd expect.
Week 08 Recap
Big-Oh describes how work grows with n, not seconds on a clock
Drop constant factors and lower-order terms: keep the dominant one
Nested loops multiply; halving the problem gives lg n
O(1) < O(lg n) < O(n) < O(n lg n) < O(n²) < O(2ⁿ)
At a million items the difference is a second versus an afternoon
Next: a09 →
This deck stands on earlier CS112 materials by Joel Adams and Victor Norman · adapted and extended by Eric Araújo