An eventual upper bound
Big-O notation describes an eventual upper bound on a function, allowing a constant multiplier. Informally, T(n) is O(f(n)) if positive constants c and n0 can be chosen so that T(n)≤c·f(n) for every n≥n0. The inequality need not hold unchanged for all small inputs. This lets an analysis focus on growth with input size, but it does not claim that constants never matter in practice. State what resource T measures, such as comparisons, memory use, or another explicitly defined cost.
Bounding a simple function
For T(n)=3n+4, choosing c=7 works for n≥1, so the function is O(n). It is also O(n²), which is a valid but looser upper bound. Big-O does not mean exactly the same growth rate. A tight asymptotic bound is expressed with notation such as Theta when the corresponding lower bound also holds. Therefore, reading O(n²) as proof that a function necessarily grows quadratically is a mistake. Ask whether the author supplied only an upper bound or also established a matching lower bound.
Worst-case is a separate choice
Worst-case, expected, and amortized analyses select different quantities to bound. Big-O itself does not mean worst-case. Applying it to a worst-case cost function gives a worst-case upper bound; applying it to an expectation gives a bound on that expectation. Amortized analysis instead accounts for a sequence of operations. For example, an expected O(1) hash-table claim does not guarantee that every individual operation takes constant time on every input. The distributional or structural assumptions are part of the result and must travel with the notation.
Growth is not a complete benchmark
Two O(n) implementations can have different elapsed times because their constants, memory access patterns, parallelism, and setup costs differ. At a small input size, a simple quadratic implementation can even outperform an implementation with better asymptotic growth but substantial overhead. Asymptotic reasoning supplies a scaling perspective rather than replacing measurement. A useful comparison defines input size, identifies the resource being counted, and records the environment for any benchmark. Combine the mathematical model with representative measurements instead of treating a notation hierarchy as a universal ranking of real programs.
Keep both input dimensions in the bound
A traversal of an n-row, m-column table takes O(nm) element inspections when inspecting one element has constant cost. If m is always fixed at eight, the cost as a function of n is O(n). If m grows with n and m equals n, the same loop structure yields O(n²). Two nested loops therefore do not automatically establish a quadratic bound in one unspecified input size. If each iteration compares strings of length k, inspect whether treating that comparison as constant is justified. Define the input dimensions and primitive cost model before dropping variables or choosing a dominant term. This also makes a benchmark’s scaling assumptions easier to test.