Big-O, Θ, Ω and the cost model

Big-O is an asymptotic upper bound, not a synonym for worst case. Identify the function: worst, average, best or amortised cost. For 3n²+7n+4, sufficiently large n permits f(n)≤cn². Θ supplies matching upper and lower bounds; Ω supplies a lower bound only.

Nested syntax does not prove quadratic cost. A constant inner loop stays linear, and two forward-only pointers may move at most 2n times across the entire run. Sequential costs add; independent nested repetitions multiply. log₂ n measures repeated halving. Logarithm bases differ by a constant factor for asymptotic classification.

Separate input, output and auxiliary space. Producing an n-element result can require O(n) output space while using O(1) auxiliary space. Python arbitrary-precision arithmetic depends on bit length; state when you are using a unit-cost RAM model.

Building the mathematical argument

For f(n)=3n²+7n+4 and n≥1, we have 7n≤7n² and 4≤4n². Thus f(n)≤14n²: c=14 and n₀=1 satisfy O(n²). Since f(n)≥3n², the tight bound is Θ(n²). O(n³) is also true but loose. O(n²) does not mean exactly n² executed steps.

An inner loop running i times yields 0+1+…+(n−1)=n(n−1)/2 operations. A loop that halves its counter needs a different count. An n-iteration outer loop with log n inner work gives Θ(n log n). A sliding window may contain nested while loops yet take Θ(n), because each pointer advances at most n times overall.

Growth	Approximate effect of doubling n	Reason
log n	A constant extra step	Halving the range
n	2×	One scan
n log n	Slightly more than 2×	Linear work on logarithmic levels
n²	4×	All pairs
2ⁿ	A factor of 2ⁿ	All subsets

These ratios describe dominant asymptotic terms. Real latency includes allocation, caches, JIT, scheduling and I/O. Record input distributions, warm-up, repetitions and environment. A faster algorithm at 100 elements may lose at ten million.

Three practice stages

Foundation: Compare three consecutive n loops with three nested n loops: Θ(n) versus Θ(n³).

Intermediate: Bound total advances in a two-pointer algorithm where j is never reset and only increases.

Advanced: Replace unit-cost large-integer multiplication with a bit-cost model. Separate item count from bit length. The algorithm can remain identical while its complexity expression changes.

def triangular_work(n):
    count = 0
    for i in range(n):
        for j in range(i + 1):
            count += 1
    return count
assert triangular_work(4) == 10