Two exact operation-count models are f(n)=3n²+2n and g(n)=3n², where the positive integer n is an input size. The first model always performs more operations. Yet its extra work becomes a smaller fraction of the main quadratic count. Which kind of approximation would justify replacing one count with the other?
Calculate both the absolute error |f−g| and the relative error |f−g|/g. A vertical distance on a plot represents the first, not automatically the second.
Input n
f(n)
g(n)
Absolute error
Relative error
2
16
12
4
1/3
10
320
300
20
1/15
100
30200
30000
200
1/150
Predict
Predict whether a relative error below 1% will eventually remain below 1%, even though the absolute error keeps increasing. Here the ratio f/g=1+2/(3n), so the relative error is exactly 2/(3n). It is below 1/100 whenever n>200/3; every integer n≥67 works. This is an all-later-input bound, not a pattern guessed from the three displayed rows.
Now replace the first count by h(n)=6n². Its ratio to g is always 2. These counts have the same quadratic growth up to constant factors, but their relative error is always 1. We need different notation for “within constant factors” and “ratio approaches one.”
Experiment
Choose a relative tolerance, first 5% and then 0.1%. Solve 2/(3n) below that tolerance and choose the least positive integer threshold. For 5%, all n≥14 work; for 0.1%, all n≥667 work. Verify the preceding integer fails each strict inequality. Keep the tolerance and threshold beside your claim.
Next make two columns for a(n)=n(3+(−1)ⁿ) and b(n)=n. Compute their ratio for n=1 through 6. The ratio alternates between 2 and 4 forever, rather than approaching a single value. Write a correct bound that covers every row, then explain why extending the table to a million rows would still not replace the formula-based proof.
These paper calculations concern stipulated counts. They are not hardware timings. A model’s order of growth does not specify its constant costs, memory use or real-machine overhead.
Understand
We work with sequences on positive integers that are eventually positive: each becomes positive for every n beyond some fixed threshold. This permits division by a positive reference g. A finite initial irregularity does not affect any of the following definitions.
f=O(g) means there exist a constant C>0 and an integer N such that, for every n≥N, f(n)≤Cg(n). The same constant must work for all later inputs. The notation describes an eventual upper bound, not equality or a tight estimate.
f=Θ(g) means there exist constants c>0, C>0 and an integer N such that c g(n)≤f(n)≤C g(n) for every n≥N. Thus the ratio stays bounded above and bounded away from zero. It need not have a limit: the alternating ratio 2,4 above satisfies Θ with c=2 and C=4.
f=o(g), pronounced “little-o,” means for every ε>0 there exists an integer N such that f(n)<εg(n) for every n≥N. Equivalently f/g tends to zero. Compare the quantifiers with O: one convenient constant is not enough; every positive tolerance must eventually work. For example n=o(n²), because 1/n becomes smaller than any positive ε once n>1/ε. Yet 2n² is O(n²), not o(n²).
f~g, asymptotic equivalence, means f/g tends to 1: for every ε>0 there exists N such that |f(n)/g(n)−1|<ε for every n≥N. It says the relative error tends to zero. Our initial f and g satisfy this, using any integer N>2/(3ε). Taking ε=1/2 shows that every asymptotically equivalent positive pair is Θ: eventually its ratio lies between 1/2 and 3/2. The converse fails both for the constant ratio 2 and for the alternating ratio 2,4.
There are safe algebraic rules with explicit hypotheses. If f~g and u~v, with all four sequences eventually positive, then fu~gv, since its ratio is the product (f/g)(u/v). If each factor differs from 1 by at most δ, the product differs by at most 2δ+δ², which tends to zero. For sums, the relative error is bounded by
|(f+u)−(g+v)|/(g+v) ≤ (|f−g|+|u−v|)/(g+v).
Once both individual relative errors are below ε, the right side is below (εg+εv)/(g+v)=ε. This works even when g/v oscillates. Positivity prevents cancellation in the denominator.
Subtraction loses that protection. Take f=n+1, g=n, u=n and v=n−2, for n≥3. We have f~g and u~v, but f−u=1 while g−v=2. Their ratio is 1/2, not 1. Approximating each large term relatively well need not approximate their small difference relatively well.
Apply
Audit a claim based on a finite plot. Suppose every displayed point through n=M agrees with n². One extension can continue as n² forever; another can change to n³ after M. Both match all recorded data, yet only one is Θ(n²). A general bound needs a declared formula, a proved invariant or other all-input information, not just a longer display.
Also check the scale before saying an error is small. Let g(n)=1/n and f(n)=2/n. Their absolute difference tends to zero, but their relative difference is always 1. Conversely, our initial operation counts have diverging absolute difference and vanishing relative difference. Write which error your application actually needs.
Finally, logarithms require care. The positive sequences eⁿ and e²ⁿ have logarithms n and 2n, so the logarithms are Θ of one another although the original ratio is eⁿ. Even asymptotic equivalence of logarithms alone is insufficient: ln(exp(n+√n))/ln(exp(n))=1+1/√n tends to 1, while the original ratio exp(√n) diverges. In contrast, if ln f−ln g tends to zero, continuity of the exponential gives f/g=exp(ln f−ln g) tending to 1. Exponentiating preserves a vanishing absolute log difference, not every relative statement about logarithms.
Big-O comparison is not a total ranking
A bounded oscillating ratio can still give Θ, as above. A stronger failure is possible: neither sequence is O of the other. Define f(n)=n² at odd n and f(n)=n at even n; reverse those choices for g. On odd indices f/g=n grows without bound; on even indices g/f=n does. Both sequences are positive, yet neither bounds the other eventually by a fixed multiple.
Write the full negation: f is not O(g) means that for every C>0 and every integer threshold N there exists an integer n≥N such that f(n)>C g(n). Choose an odd n larger than both C and N for the first direction, and an even one for the reverse. A single large ratio does not refute O, because its witness might occur before an allowed threshold. Nor does failure of a ratio limit alone refute O: the bounded alternating example earlier still satisfies Θ.
The parity example decreases at some steps. That is not essential: even two strictly increasing positive integer sequences can be incomparable.
A construction in which both sequences increase
Start F₀=G₀=1. For n≥1, let rn=n+1. At an odd step set G_n=G(n−1)+1 and then Fn=r_n G_n. At an even step set F_n=F(n−1)+1 and then G_n=r_n F_n. The order within each step matters: multiply the newly incremented value, not its previous value.
The first four pairs are (4,2), (5,15), (64,16), (65,325). Check strict increase of both coordinates. At an odd step after the first, the preceding even step has G(n−1)=r(n−1)F(n−1) with r(n−1)≥2. Incrementing G and multiplying it by r_n≥2 makes the new F exceed its old value; G also increases by one. The even step is symmetric, and the first step is checked from (1,1). This induction proves both sequences increase forever, rather than relying on the displayed rows.
At odd n the exact ratio F_n/G_n is n+1. At even n the reciprocal G_n/F_n is n+1. Given any proposed C and threshold N, choose an odd n beyond both to defeat F=O(G), and an even n beyond both to defeat G=O(F). Monotonicity of each sequence does not make their relative growth monotone. The ratios have limsup infinity and liminf zero in each direction; neither has an ordinary finite limit.
Both sequences increase; neither must bound the other
Predict whether either displayed ratio exceeds C=4. Exact integer comparisons test F_n>C G_n and G_n>C F_n; the plot uses approximate ratios on shared fixed axes.
Solid navy: F/G. Dashed red: G/F. First displayed F>C G witness: 5. First displayed G>C F witness: 4. No displayed witness is not a proof of an eventual bound; a witness at one index does not rule out a later threshold.
n
F_n
G_n
r_n
0
1
1
1
1
4
2
2
2
5
15
3
3
64
16
4
4
65
325
5
5
1956
326
6
6
1957
13699
7
Compare the two infinite constructions
For every C and every threshold N, arbitrarily late odd n have F/G=n+1>C and arbitrarily late even n have G/F=n+1>C. Thus both O claims fail.
At most13 exact integer rows; temporary state. These are constructed sequences, not measured runtimes. The proof below controls all later indices; the bounded display illustrates it.
The real hypothesis is growth on both subsequences
The same recurrence works for any finite real multipliers r_n≥2, producing strictly increasing positive real sequences; integer multipliers keep integer values. The ratios are r_n on the step’s dominant side and 1/r_n on the other. Thus incomparability requires unbounded odd multipliers and unbounded even multipliers separately. Unboundedness on a parity also gives witnesses beyond every threshold: a finite prefix has a finite maximum, so arbitrarily large values cannot all occur there.
For a changed rule, keep r_n=n+1 at odd indices but set r_n=2 at every even index. Both sequences still increase. The odd F/G ratios are unbounded, so F is not O(G). But G/F is2 at even indices, at most1/2 at odd indices, and1 initially. Hence G≤2F everywhere, so G=O(F). The complete multiplier sequence is unbounded, yet only one comparison fails. This counterexample diagnoses the missing parity condition rather than merely changing a few initial values.
What sort of ordering survives?
For eventually positive sequences, O is reflexive and transitive: multiply eventual upper constants and take the larger threshold. Mutual O is equivalent to Θ by combining the upper bound in one direction with the reciprocal bound in the other. After identifying sequences that are Θ-equivalent, O gives a partial order, but these constructions show it is not a total order. None of this says that the constructed sequences are actual running times of specific algorithms; no machine measurements were made.
The discrete source audit’s Spring2015 final motivates the incomparable-growth construction taught here. These examples and the monotone recurrence are original follow-through, with both negated quantifier statements supplied. Public worked arguments and a bounded graph do not establish independent learner performance.
Recover an accumulated polynomial, then certify it
Suppose stage k uses k² abstract work units. The cumulative totals for n=0, 1, 2, 3 are 0, 1, 5, 14. A cubic candidate P(n)=a n³ + b n² + c n has constant term zero because there is no work at n=0. Its increment is 3a n² + (−3a + 2b)n + (a − b + c). To equal n² for every n, its coefficients must give a=1/3, b=1/2, c=1/6. Thus P(n)=n(n+1)(2n+1)/6.
This calculation is a proof once the increment identity and initial value are checked: if P(n−1) is the previous cumulative sum, adding n² gives P(n). Induction proves the formula for every nonnegative integer. Merely matching four observed totals does not justify assuming the true total is cubic.
Matching samples versus proving every increment
Sum k to the power d for k from1 through n. At n=0 the sum is empty and equals zero. All values here are exact small integers or rational values; no fitted floating-point solver is used.
Numerator coefficients, constant first: 0, 1, 3, 2. Divide this polynomial by 6. Its degree is 3.
Increment residual means candidate at n minus candidate at n−1 minus n to the power d. Its numerator coefficients are 0, with the same denominator.
Identity certified: initial value zero and every residual coefficient zero.
The alteration is the product of n−j for j=0 through d+1. It vanishes at the first d+2 nodes, but exceeds the allowed degree d+1. Predict its first mismatch before reading later rows.
n
Initial sample?
Direct sum
Candidate
Increment residual
0
yes
0
0
initial value only
1
yes
1
1
0
2
yes
5
5
0
3
yes
14
14
0
4
no
30
30
0
5
no
55
55
0
6
no
91
91
0
7
no
140
140
0
8
no
204
204
0
9
no
285
285
0
10
no
385
385
0
11
no
506
506
0
12
no
650
650
0
The coefficient identity certifies all positive integers; thirteen displayed rows alone do not. Settings are temporary and are not saved proof or mastery evidence.
Why a polynomial sum exists, and when interpolation is sufficient
Define the backward difference of P to be P(n)−P(n−1). For a leading term a n^r with r≥1, the binomial theorem makes its difference have leading term r a n^(r−1). Lower powers cannot change that leading coefficient. Given any real polynomial q of degree d, choose a leading term of degree d+1 whose difference matches q’s leading term. Subtract that difference from q; the remainder has lower degree. Repeat down to constants. This finite elimination constructs P with difference q. Adjust its constant to enforce P(0)=0, without changing its difference. For q with leading coefficient a, P has leading coefficient a/(d+1).
Uniqueness follows too: the difference of two candidates has zero backward difference. A nonconstant polynomial would have a nonzero leading difference, so their difference is constant; their shared value at zero makes that constant zero. Induction now identifies this unique polynomial with the sum of q(k) from k=1 through n. This is a polynomial identity over the reals, not a claim about sums at negative stage counts.
After this existence and degree bound have been proved, d+2 distinct cumulative values uniquely recover a polynomial of degree at most d+1: the difference of two fits would have d+2 roots but degree at most d+1. Without the degree bound, adding a multiple of the product of n minus each sample node gives another polynomial agreeing at every sample. The inspector exposes exactly this failure. The theorem, rather than the finite table, permits interpolation as a recovery method.
Positive powers: a growth bound is not a leading constant
Let a be a fixed positive real exponent and let S(n) sum k^a for k=1 through n. Every term is at most n^a, giving S(n)≤n^(a+1). For n≥2, at least n/2 indices lie between the ceiling of n/2 and n. Each contributes at least (n/2)^a. Therefore S(n)≥n^(a+1)/2^(a+1). These explicit positive constants prove S(n)=Θ(n^(a+1)), without requiring a to be an integer or using a polynomial formula.
The bounds alone do not establish asymptotic equivalence to n^(a+1), nor identify its coefficient. If integration is available, increasing rectangles give the sharper bounds: the integral of x^a from0 to n is at most S(n), and S(n) is at most the integral from1 to n+1. These are n^(a+1)/(a+1) and ((n+1)^(a+1)−1)/(a+1). Divide by n^(a+1) and squeeze to obtain the limit 1/(a+1). Hence S(n) is asymptotically equivalent to n^(a+1)/(a+1). For a=2, the exact formula above gives the same constant1/3. The block proof establishes order; the rectangle argument supplies the stronger leading constant. These are abstract counts, not measured execution times.
Continue
Use the written tasks to supply explicit thresholds, disprove a ratio limit using even and odd subsequences, and test cancellation and shrinking-reference examples. Record the domain, positivity threshold and quantifier order before applying a comparison rule.
Later sum and product estimates can use these distinctions to report exactly what an approximation guarantees. An upper bound, a constant-factor estimate and a vanishing relative error are different mathematical results; none alone is a measured performance claim.
Apply · explain · revise
Practice and reasoning
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
Recover the polynomial for S(n)=Σ from k=1 through n of k² by matching coefficients in P(n)−P(n−1)=n² and imposing P(0)=0. Prove the resulting identity for all n≥0. Explain why four initial values alone are insufficient without a degree hypothesis, and construct a competing polynomial agreeing at n=0, 1, 2, 3.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
For fixed real a>0, prove explicit two-sided bounds showing Σ k^a=Θ(n^(a+1)). Does this prove asymptotic equivalence to n^(a+1)? Use increasing integral rectangles to obtain the correct leading constant, explaining which conclusion is stronger.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Let f(n)=5n²+4n+9 and g(n)=5n² for positive integers n. Prove f=Θ(g) with explicit constants and threshold. Then prove f~g by giving a threshold N for every ε>0. Determine whether f−g tends to zero, and explain why your answers are compatible.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Set f(n)=n(2+(−1)^n) and g(n)=n. Prove f=Θ(g), decide whether f/g has a limit, and decide f~g, f=o(g), and g=o(f). Explain why nonexistence of a ratio limit does not refute Θ.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
State the eventual inequality definitions of f=O(g) and f=o(g) for eventually positive sequences. Prove n=o(n²) with explicit quantifiers, prove n² is not O(n), and give a positive example showing that O does not imply little-o.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Assume f,g,u,v are eventually positive, f~g and u~v. Prove fu~gv and f+u~g+v. For the sum give a relative-error bound that works even if g/v has no limit. Does this prove f−u~g−v whenever both differences are eventually positive? Give a counterexample if not.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
For f(n)=e^(n+√n) and g(n)=e^n, prove ln f~ln g but f is not O(g). Then prove the stronger condition ln f−ln g→0 implies f~g for positive sequences. Distinguish a small relative error in logarithms from a small absolute error in logarithms.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
A plot shows f(n)=n² for each observed integer1≤n≤M, where M≥1 is fixed. Construct two positive sequences agreeing with every observation, one asymptotic to n² and another not even O(n²). Prove both claims. Separately, a model reports an absolute error |f(n)−g(n)|≤1/n with g(n)=1/n². Does this imply f~g? Give a positive counterexample and identify a sufficient replacement condition.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Construct positive sequences f,g such that neither f=O(g) nor g=O(f). State and prove both fully negated quantified claims. Contrast your example with f(n)=n(2+(−1)^n), g(n)=n. Explain why either one large ratio or a nonconvergent ratio is insufficient.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Starting F0=G0=1, at odd n set G_n=G_(n−1)+1 and F_n=(n+1)G_n; at even n set F_n=F_(n−1)+1 and G_n=(n+1)F_n. Prove both sequences are strictly increasing integers, compute the first four pairs, and prove they are incomparable under O. Replace the multiplier by2 at every even step: classify both O directions and explain which proof obligation changes.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
