Big-O notation
Big-O notation is a tidy shorthand for how fast something grows as the input gets large, written O(...) — read 'order of.' It is the language we use to say 'this algorithm is linear' as O(n), 'this one is quadratic' as O(n^2), or 'this one barely slows down' as O(log n). The single most useful instinct to build: Big-O ignores small details and constants, and keeps only the term that dominates when n is huge. Picture two cars. One is faster off the line but tops out; the other accelerates forever. For a short sprint the first wins, but on a long enough road the second always pulls ahead. Big-O is about the long road — the behavior as n grows without bound.
Two simple rules make it click. First, drop constant factors: 3n + 50 is just O(n), because tripling the work or adding a fixed 50 does not change the shape of the curve, only its steepness, and steepness is a hardware detail. Second, keep only the biggest term: n^2 + n + 100 is O(n^2), because once n is large the n^2 part dwarfs everything else. So O(n^2) does not mean 'exactly n^2 steps' — it means 'grows no faster than some constant times n^2.' It is an upper bound on the growth rate, not a step count.
A useful ladder, from kindest to cruelest as n grows: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) (the speed of good sorts), O(n^2) quadratic, and O(2^n) exponential (which becomes hopeless very fast). Don't let the symbols intimidate you: Big-O is just a promise about scaling. It deliberately throws away the small stuff so you can compare two algorithms by their essential character, and pick the one that will still be standing when the input gets big.
long long sum = 0; for (int i = 0; i < n; ++i) // loop runs n times sum += a[i]; // O(n) total work, O(1) extra space
Summing n numbers does ~n additions: O(n) time, O(1) extra space.
O is an upper bound (grows no faster than). Its siblings: Omega is a lower bound, Theta is a tight bound (both at once). In everyday speech 'O' usually means the worst-case growth.