Growth of Functions
By the end of this lesson you will be able to read and write Θ, O, Ω, o and ω notation correctly, find the constants (c, c₁, c₂, n₀) that prove or disprove a claim, and reason about the standard functions (polynomials, exponentials, logs, factorials, Fibonacci) that these notations are almost always applied to. This lesson assumes M01 · Maths for Algorithms (powers, logs, floors/ceilings, the growth race, summations) — read that first if any of those words are unfamiliar; we build directly on top of it and will link back instead of repeating it.
1. Why we need a notation for growth at all
2n² rupees to deliver to n houses, Company B charges 50·n·lg n rupees. For n = 10 houses, A is far cheaper (200 vs about 1,661 — A is roughly 8× cheaper). For n = 10,000,000 houses, A costs about 2×10¹⁴ rupees while B costs about 1.16×10¹⁰ — B is now over 17,000× cheaper. The exact constants (2, 50) stopped mattering; what mattered was the shape of the formula (n² vs n lg n) once n got large. Asymptotic notation is a precise vocabulary for talking about that shape — "how does the cost behave as the input grows without bound?" — while deliberately throwing away the constant factors and small-n details that a real machine's speed would swallow anyway (even a machine 1,000× faster running the 2n² method loses to the 50n lg n method on a slow machine once n reaches the millions — see M01 section 4).Dart — the two price formulas as functions. firstNWhereBWins() finds where B becomes cheaper for good (n = 190 houses; checked for every later n up to 106).
Input size → what is feasible: each formula is O(1) per n, so scanning n = 3 … 190 or testing n = 107 is instant; the scan is a Θ(n)-step loop, fine for n up to ~108 in a second.
Every notation in this lesson is a set membership statement about functions f, g : ℕ → ℝ (or, informally, "f is in the set of functions that grow like g"). We always write f(n) = Θ(g(n)) as an abuse of the equals sign — it really means f(n) ∈ Θ(g(n)) — but that abuse is universal in every algorithms course and paper, so we use it too.
2. Θ-notation: the tight sandwich
f(n) as a wiggly, hard-to-describe line. Θ(g(n)) says: "there is a floor c₁·g(n) and a ceiling c₂·g(n), both shaped like g, such that f(n) is squeezed between them for every n past some starting point n₀." Small, irregular wiggling near the start (small n) doesn't matter — only the shape once n is "large enough" matters, and the sandwich must hold forever after that point, not just occasionally.Formally: for a given function g(n),
Θ(g(n)) = { f(n) : ∃ positive constants c₁, c₂, n₀ such that 0 ≤ c₁g(n) ≤ f(n) ≤ c₂g(n) for all n ≥ n₀ }.
We say g(n) is an asymptotically tight bound for f(n). (This definition requires f and g to be asymptotically nonnegative — nonnegative for all sufficiently large n — which every running time naturally is.)
A worked example: f(n) = 3n² − 10n is Θ(n²), witnessed by c₁ = 1/2, c₂ = 3, n₀ = 4. Play with your own c₁, c₂, n₀ below and watch whether the sandwich actually holds — the plot is drawn directly from the numbers you pick, not from a canned answer:
Dart — the sandwich as code. sandwich tests c₁·g(n) ≤ f(n) ≤ c₂·g(n) for every n in a range (the “for all n ≥ n₀” of the definition, checked up to a limit); tightestConstants(4, …) finds the best c₁ and c₂ numerically (1/2 and just under 3); smallestN0 finds the smallest n₀ for given constants (4); quadraticWitness is the keypoint’s c₁ = a/4, c₂ = 7a/4, n₀ recipe, checked on five different quadratics. A finite scan is evidence that finds the constants; the algebra is what proves them for all n.
Input size → what is feasible: each check is a Θ(last − n₀) loop: last = 106 is instant, 109 takes seconds — use algebra, not a scan, for symbolic n.
an² + bn + c with a > 0 is Θ(n²) — this generalizes: c₁ = a/4, c₂ = 7a/4, n₀ = 2·max(|b|/a, √(|c|/a)) always works (a recipe you can check by algebra). More generally, every polynomial of degree d with a positive leading coefficient is Θ(nd) — the highest-degree term always wins the sandwich once n is large enough, and every lower-degree term gets absorbed into the "for large enough n" slack.3. O-notation and Ω-notation: one-sided bounds, and the tight-bound theorem
Formally: O(g(n)) = { f(n) : ∃ c, n₀ > 0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀ } (upper bound), and
Ω(g(n)) = { f(n) : ∃ c, n₀ > 0 such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n₀ } (lower bound). Since Θ requires both, Θ(g(n)) ⊆ O(g(n)) and Θ(g(n)) ⊆ Ω(g(n)). In the player above, the red ceiling line c₂n² is the O half of the picture and the green floor line c₁n² is the Ω half — Θ needs both.
Dart — O and Ω as range checks, and the tight-bound theorem as one line (isTheta = isBigOmega && isBigO). smallestN0BigO finds n₀ for a chosen c: for 100n + 5 it returns 1 for c = 105, 5 for c = 101, and null for c = 100 (no n₀ exists). insertionSortComparisons counts key comparisons: A = [3, 8, 1, 5, 9, 2] takes 11; a sorted array of n = 100 takes 99 (n − 1) but a reversed one takes 4,950 (n(n − 1)/2) — so insertion sort is O(n²) overall but not Θ(n²).
Input size → what is feasible: insertion sort with n ≤ 104 (≤ 5·107 comparisons) runs in well under a second; n = 106 would need ~5·1011 — switch to merge sort.
f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)). This is the formal justification for describing an algorithm's worst-case running time with O (a guarantee that holds for every input — e.g. insertion sort is O(n²) on all inputs) while reserving Θ for a claim that is tight for a specific case: insertion sort's worst case is Θ(n²) (reverse-sorted input actually takes that long), but its best case is Θ(n) (already-sorted input) — so insertion sort overall is not Θ(n²) on every input, even though its worst case is.Ω(n²), and if you mean it is tight, it's Θ(n²).4. Disproving a Θ-claim: 6n³ ≠ Θ(n²)
This is a quick counter-example: no constant ceiling can hold forever. Pick any candidate c₂ you like below; the animation will find exactly where 6n³ breaks through it, and explain why it can never come back down once it has crossed (because 6n³ / n² = 6n is strictly increasing — once the ratio is above c₂ it stays above c₂ forever):
Dart — firstBreak(c₂) scans for the first n where 6n³ > c₂n²; firstBreakClosed is the algebra (6n > c₂ ⇒ n = ⌊c₂/6⌋ + 1) and the checks confirm they agree (c₂ = 1000 → 167, c₂ = 106 → 166,667); staysBroken confirms the ratio 6n never comes back below c₂.
Input size → what is feasible: the scan is Θ(c₂/6) steps — c₂ up to ~108 is fine, so the page caps c₂ at 1012 and uses the closed form.
f(n) = Θ(g(n)), it is enough to show that f(n)/g(n) is unbounded (no constant ceiling works, ruling out O) or that it approaches 0 (no constant floor works, ruling out Ω) as n → ∞. Here 6n³/n² = 6n → ∞, so no O(n²) ceiling exists — that alone is enough to rule out Θ(n²), since Θ needs both.5. o-notation and ω-notation: strict bounds
< and > versus ≤ and ≥.Formally: f(n) = o(g(n)) means for every constant c > 0, there exists n₀ such that 0 ≤ f(n) < c·g(n) for all n ≥ n₀ — equivalently, lim_{n→∞} f(n)/g(n) = 0. And f(n) = ω(g(n)) means for every c > 0, there is an n₀ with 0 ≤ c·g(n) < f(n) for all n ≥ n₀ — equivalently, lim_{n→∞} f(n)/g(n) = ∞. Watch the ratio itself run toward 0 or toward infinity as n grows:
Dart — o and ω say “for EVERY c”, so the code searches a separate n₀ for each c: n0SmallO(c) returns ⌊2/c⌋ + 1 (c = 0.01 → 201) and n0Omega(c) returns ⌊2c⌋ + 1 (c = 1000 → 2001), both verified against the algebra. For 2n² the search finds no n₀ with c = 1, which is exactly why 2n² ≠ o(n²).
Input size → what is feasible: each search scans down from limit, a Θ(limit) loop; c ≥ 10-3 needs limit ≈ 2·103 and is instant.
2n = o(n²) (ratio 2/n → 0) but 2n² ≠ o(n²) (ratio stays at constant 2, never shrinks to 0). And n²/2 = ω(n) (ratio n/2 → ∞) but n²/2 ≠ ω(n²) (ratio stays at constant 1/2). o ∩ ω = ∅ — a function can never be both strictly smaller and strictly bigger than the same g.6. Properties, "abuse of notation", and why there's no trichotomy
| Notation | Real-number analogy | Properties that hold |
|---|---|---|
| O(g) | ≤ | transitive, reflexive |
| Ω(g) | ≥ | transitive, reflexive |
| Θ(g) | = | transitive, reflexive, symmetric: f=Θ(g) ⇔ g=Θ(f) |
| o(g) | < | transitive (not reflexive) |
| ω(g) | > | transitive (not reflexive) |
Transpose symmetry links the "upper" and "lower" families: f = O(g) ⟺ g = Ω(f), and f = o(g) ⟺ g = ω(f). So every fact about O has a mirror-image fact about Ω, and every fact about o mirrors a fact about ω — you never need to memorize both sides separately.
2n² + 3n + 1 = 2n² + Θ(n) means "there exists some function h(n) ∈ Θ(n) such that 2n²+3n+1 = 2n²+h(n)" (here h(n) = 3n+1, which is indeed Θ(n)). When such expressions appear on both sides — like 2n² + Θ(n) = Θ(n²) — read left to right: "for any choice of anonymous function on the left, there is some choice on the right making the equation true." This convention is also why Σᵢ O(i) can validly denote one single anonymous function, not "the sum of n different anonymous functions".a<b, a=b, a>b always holds. Asymptotic notation has no such guarantee: n and n^(1+sin n) are incomparable — neither is O of the other, because sin n oscillates between −1 and 1 forever, so n^(1+sin n) swings between roughly n⁰=1 and n² infinitely often as n grows, never settling into a stable ratio with n in either direction.Dart — the properties as functions on witnesses (c, n₀): composeBigO is transitivity (c = c₁c₂, n₀ = max), transposeBigO is f = O(g) ⇔ g = Ω(f) (c → 1/c), symmetricTheta is Θ-symmetry, and incomparableCounts counts, for n = 1000 … 106, how often n^(1+sin n)/n is above 100 and how often below 1/100 — each happens about 380,000 times in that range, so neither function is O of the other (no trichotomy). The page’s identity 2n² + 3n + 1 = 2n² + Θ(n) is checked with h(n) = 3n + 1 ∈ Θ(n) (c₁ = 3, c₂ = 4, n₀ = 1).
Input size → what is feasible: the counting loop is 106 pow/sin calls (about 0.1 s); a bound of 109 would take minutes.
7. Standard notations: monotonicity, floors, ceilings, mod
A function is monotonically increasing if m ≤ n ⟹ f(m) ≤ f(n) (strictly increasing if that's a strict < for m < n), and monotonically/strictly decreasing symmetrically. The floor/ceiling/mod identities you need — ⌊n/2⌋+⌈n/2⌉=n, ⌈⌈x/a⌉/b⌉=⌈x/(ab)⌉ (integers a, b > 0), a mod n = a − n⌊a/n⌋ — are already covered with an animated number-line and verified numerically in M01 section 3; we won't re-derive them here, only use them.
Dart — floors, ceilings and mod as exact integer code. Dart’s ~/ truncates toward zero (−7 ~/ 2 = −3) so floorDiv fixes the negative case (−4); modFloor(a, n) = a − n·⌊a/n⌋ agrees with Dart’s % for n > 0 (e.g. −7 mod 3 = 2); the checks cover ⌊n/2⌋ + ⌈n/2⌉ = n, ⌈⌈x/a⌉/b⌉ = ⌈x/(ab)⌉, ⌈a/b⌉ = (a + b − 1) ~/ b and x − 1 < ⌊x⌋ ≤ x ≤ ⌈x⌉ < x + 1; isMonotonicallyIncreasing / isStrictlyIncreasing test the definition on a range (⌊n/2⌋ is monotone but not strict).
Input size → what is feasible: all of these are O(1) per value with native int (64-bit, |a| < 9.2·1018); the monotonicity scans are Θ(range).
8. Polynomials and polynomially bounded functions
A polynomial p(n) = Σᵢ₌₀ᵈ aᵢnⁱ of degree d, with a_d > 0, is Θ(n^d) (Section 2's keypoint). A function is polynomially bounded if it is O(n^k) for some constant k — this is a useful category because it excludes anything that grows exponentially, and it's the dividing line the whole field of complexity theory (P vs NP) is built around.
Dart — horner evaluates p(n) = Σ aᵢnⁱ with d multiplications (coeffs[i] = aᵢ, so the array index IS the exponent); leadingRatio shows p(n)/nd → ad (for 3n³ − 20n² + 7n + 100 it tends to 3); thetaN0 finds the n₀ where (ad/2)nd ≤ p(n) ≤ 2adnd starts to hold for good (13 for that cubic).
Input size → what is feasible: Horner is Θ(d) per evaluation, so degree d ≤ 104 and n up to 106 is instant (use doubles: nd overflows a 64-bit int quickly).
9. Exponentials always beat polynomials
Dart — the exponent rules (exponentRuleError checks am·an = am+n, (am)n = amn, a−1 = 1/a on a grid), the inequality ex ≥ 1 + x (expAtLeastOnePlusX), the series ex = Σ xⁱ/i! (expSeries), and the limit (1 + x/n)n → ex (compoundLimit).
Input size → what is feasible: the series converges to double precision with 25–40 terms for |x| ≤ 2; compoundLimit needs n = 106 for 5 correct digits — the series is far cheaper.
The rule: for any real constants a > 1 and b, n^b = o(a^n) — any exponential (base > 1) beats any polynomial. Note the comparison isn't always monotonic for small n — a fast-growing polynomial like n^10 can lead a slow exponential like 1.1ⁿ for a long stretch before losing for good. Pick your own polynomial degree and exponential base and watch where the crossover really happens:
Dart — gap(n) = ln(aⁿ) − ln(nᵇ) works in log-space, so n10 and 1.1n never overflow. leadChanges(10, 1.1, 2000) returns [2, 686] — 1.1ⁿ leads at n = 1, loses from n = 2, and wins for good from n = 686; permanentCrossover finds that 686 by binary search past the minimum n* = b/ln a instead of stepping n one at a time.
Input size → what is feasible: the binary search is O(lg n) log-evaluations, so even a = 1.0001, b = 30 (crossover in the millions) is instant; the 2000-step scan is for display only.
n^10 vs 1.1ⁿ doesn't cross over for good until roughly n ≈ 686 (verified in verify/c03.dart) — 1.1ⁿ is ahead only at n = 1, then falls behind n^10 for every n from 2 to 685 (the lead changes exactly twice, at n = 2 and n = 686 — checked in the Dart panel below), because 1.1ⁿ grows so slowly at first. The theorem guarantees a permanent crossover exists; it says nothing about how small n has to be to see it.10. Logarithms (recap)
M01 section 2 already covers logs in full — what a log means, the product/quotient/power/change-of-base rules, and (critically for this chapter) why the base never matters in Big-O: since log_b n = log_2 n / log_2 b, switching bases only multiplies by a constant, and Big-O throws constants away. That's why this course almost always just writes lg n or O(log n) without specifying a base.
lg^k n = o(n^a) for any constant a > 0, no matter how small. Even (lg n)^{1000} is eventually beaten by n^{0.001}. Logs, no matter how many times you raise them to a power, are asymptotically tiny compared to any positive power of n.Dart — baseRatio(b, n) = logbn / lg n is the same number 1/lg b for every n — the code form of “the base never matters in O”; twoToLg checks 2lg n = n; polylogCrossoverLnN(k, a) finds, in terms of x = ln n, where na overtakes (lg n)k for good: (lg n)3 vs n0.5 flips for good at ln n ≈ 20.2, i.e. n ≈ 6·108, but for (lg n)1000 vs n0.001 you need ln n ≈ 1.7·107, a number n = e1.7·10⁷ that no double can store — which is why the search is done on x, not n.
Input size → what is feasible: every function is O(1) (the crossover search is 200 bisection steps); k/a must exceed e·ln 2 ≈ 1.88, otherwise na is ahead from the start and there is no crossover to find.
11. Factorials and Stirling's approximation
n! ("n factorial") counts the number of ways to arrange n distinct objects in a row — for even modest n this explodes far faster than any exponential: 20! = 2,432,902,008,176,640,000 ≈ 2.43 × 10^18, about 5.6 times the age of the universe measured in seconds (≈ 4.3 × 10^17 s). Stirling's approximation is a formula that lets you estimate n! without multiplying n numbers together, and — remarkably — the estimate gets relatively more accurate the bigger n gets, even though the absolute error grows huge.Stirling's formula: n! = √(2πn) · (n/e)^n · (1 + Θ(1/n)). Watch the factorial race against the Stirling estimate (the Dart panel below uses unbounded-precision BigInt; the animation just multiplies in a double, accurate to ~15 digits and fine up to n = 100 because a double overflows to infinity around n ≈ 171), and watch the relative error shrink even as the numbers themselves become unimaginably large:
Dart — fact is the exact BigInt n!; stirling the estimate; relativeError(n) ≈ 1/(12n) (8.4% at n = 1, 0.83% at n = 10, 0.083% at n = 100); lgFactRatio shows lg(n!)/(n lg n) climbing toward 1, i.e. lg(n!) = Θ(n lg n); factorialBeatsTwoToN finds n! > 2ⁿ from n = 4 on; the checks also confirm n! < nⁿ.
Input size → what is feasible: fact(n) is Θ(n) BigInt multiplications: n ≤ 104 is instant, n = 105 takes seconds. Converting to double only works for n ≤ 170 (171! overflows to Infinity).
n! = o(n^n) (divide both by n^n: the (1/e)^n · √(2πn) factor → 0), n! = ω(2ⁿ) (factorial eventually dwarfs any fixed-base exponential — verified with BigInt comparisons in verify/c03.dart), and lg(n!) = Θ(n lg n) (take logs of Stirling's formula: the dominant term is n lg n − n lg e, and both are Θ(n lg n) together — this is exactly why the decision-tree lower bound for comparison sorting is Ω(n lg n)).12. Functional iteration and lg* n
lg* n ("log-star of n") counts exactly that: how many times you must apply lg, feeding each answer back in, before the result drops to 1 or below.Formally: lg* n = min{ i ≥ 0 : lg^(i) n ≤ 1 }, where lg^(i) means "apply lg, i times in a row" (and lg^(0) n = n, no application at all). Try any starting number, however astronomically large:
Dart — lgIterates(65536) = [65536, 16, 4, 2, 1], so lg* 65536 = 4 (the count of applications). For numbers too big for a double, lgBig uses the BigInt bit length (lg n = (bitLength − 53) + lg of the top 53 bits), so lgStarBig(2^65536) = 5 — the page’s 19,729-digit number is handled exactly in one step.
Input size → what is feasible: any n up to 263 − 1 (a Dart int) needs at most 5 loop iterations; BigInts with 107 bits are fine too, since only the bit length matters.
lg* 2 = 1, lg* 4 = 2, lg* 16 = 3, lg* 65536 = 4, and even for 2^65536 — a number with 19,729 decimal digits — lg* is only 5. Each application of lg collapses the number's size so violently (turning "the number of digits" into roughly "the number of digits of the number of digits") that lg* essentially never exceeds 5 for any n you could ever write down or store. It appears in the analysis of the union-find (disjoint-set) data structure: with union by rank and path compression the amortized cost per operation is O(lg* n) (a loose bound — the union-find analysis proves the even slower inverse-Ackermann α(n)).13. Fibonacci numbers and the golden ratio
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …. As you go further out, the ratio between consecutive Fibonacci numbers settles down to a single, famous constant: the golden ratio φ = (1+√5)/2 ≈ 1.61803….Formally: F₀=0, F₁=1, Fᵢ=Fᵢ₋₁+Fᵢ₋₂. Let φ = (1+√5)/2 and φ̂ = (1−√5)/2 ≈ −0.61803 (the two roots of x² = x + 1). The closed form (and its round-off version): Fᵢ = (φⁱ − φ̂ⁱ)/√5 = round(φⁱ/√5), since |φ̂| < 1 makes the φ̂ⁱ term vanish as i grows. Watch the ratio Fᵢ/Fᵢ₋₁ converge:
Dart — fibRec is the direct recursive definition; fibCalls(n) counts its calls and equals 2F(n+1) − 1 = Θ(φⁿ) (2,692,537 calls for n = 30; each extra n multiplies the count by about φ); fibMemo computes each F(k) once (Θ(n)); fibClosed(i) = round(φⁱ/√5) is the round-off form, valid because |φ̂ⁱ/√5| < 1/2 (phihatTerm), exact in doubles up to i = 70.
Input size → what is feasible: fibRec: n ≤ 40 (~3·108 calls, seconds) — n = 50 would take minutes; fibMemo: n up to ~104 (recursion depth!); beyond that use the O(lg n) matrix method in the question bank.
Fᵢ = round(φⁱ/√5), Fibonacci numbers grow exponentially (base φ), i.e. Fᵢ = Θ(φⁱ) — very different from the polynomial or logarithmic growth we've mostly discussed. This is exactly why the naive recursive Fibonacci algorithm (call fib(n-1)+fib(n-2) with no memoization) takes Θ(φⁿ) time — exponential — while the matrix-exponentiation method in the question bank below computes the same number in only O(lg n) time.14. Ranking functions by growth
Here is a smaller version worked step by step — watch each comparison decide the order the same way you would by hand: evaluate both sides at a large n and see which one is bigger:
Dart — every function as ln f(n) so nothing overflows; rankByGrowth(n) sorts them by that value and returns 1, lg lg n, lg n, √n, n, n lg n, n², 2ⁿ at n = 104 and n = 106 — the same order as the page’s selection game. tieGap shows 2lg n and n have identical logs: a tie (Θ of each other) needs the same value, not a strict order. Evaluating at one large n is a sanity check, not a proof — a proof uses limits of f/g.
Input size → what is feasible: O(k lg k) for k functions per n — any n ≤ 10300 works in log-space, but n must be big enough that all crossovers have passed (1.1ⁿ vs n10 would need n ≥ 686).
1 ≺ lg lg n ≺ lg n ≺ √n ≺ n ≺ n lg n ≺ n² ≺ 2ⁿ, where ≺ means "is o( )of" (strictly slower than). Every ≺ here is strict (o-notation) — none of these 8 happen to be Θ of each other, so a clean total order exists for this particular set. The general strategy for a bigger list: group functions into "clearly polynomial", "clearly polylog", "clearly exponential/factorial" families first using the theorems above (log beats no positive power of n, no exponential loses to any polynomial, factorial beats every fixed-base exponential), then sort within each family using exponents/bases.Θ of EACH OTHER, not one strictly ahead of the other — e.g. lg(n!) and n lg n are Θ of each other (Section 11's keypoint: lg(n!) = Θ(n lg n)), and 2^(lg n) equals n exactly (by the identity a^(log_b c) = c^(log_b a) from M01, with a=b=2, c=n). When you rank the real list, functions like these form an equivalence class — they are tied, and the model answer connects tied entries with "=" instead of forcing them into a strict ≺ chain. The 8-function example above was chosen to have no ties, so the selection-game animation can show a clean strict order first — don't assume a bigger list is always tie-free.Quiz
Interview questions
Cheat sheet
| Notation | Meaning | Analogy |
|---|---|---|
Θ(g) | tight bound: c₁g ≤ f ≤ c₂g for n≥n₀ | = |
O(g) | upper bound: f ≤ c·g for n≥n₀ | ≤ |
Ω(g) | lower bound: f ≥ c·g for n≥n₀ | ≥ |
o(g) | strict upper: f/g → 0 | < |
ω(g) | strict lower: f/g → ∞ | > |
| Fact | Statement |
|---|---|
| Tight-bound theorem | f=Θ(g) ⟺ f=O(g) and f=Ω(g) |
| Transpose symmetry | f=O(g) ⟺ g=Ω(f); f=o(g) ⟺ g=ω(f) |
| Polynomial | degree d, leading coeff >0 ⟹ Θ(n^d) |
| Exponential beats polynomial | n^b = o(aⁿ) for any constant a>1 |
| Log beats no positive power | lg^k n = o(n^a) for any constant a>0 |
| Stirling | n! = √(2πn)(n/e)ⁿ(1+Θ(1/n)); n!=o(nⁿ), n!=ω(2ⁿ), lg(n!)=Θ(n lg n) |
| lg* n | times lg must be applied to reach ≤1; ≤5 for any practical n |
| Fibonacci | Fᵢ = round(φⁱ/√5), φ=(1+√5)/2≈1.618; Fᵢ=Θ(φⁱ) — exponential growth |
| No trichotomy | n and n^(1+sin n) are incomparable — neither is O of the other |