Week 08 — Big-O, precise bounds, cases, and space

The question for this week

What exactly are we promising when we say an algorithm is O(n²)?

The earlier weeks built evidence and exact operation counts. Big-O expresses an eventual upper bound. It does not say an algorithm always takes exactly n² steps, always needs quadratic time, or is slower than every linear algorithm at every input size.

Your outcomes are to write an upper bound with a constant and starting size, distinguish upper and tight bounds, analyze visible and hidden loops, name the input case, and report extra space separately from time. The original lesson also introduces Ω, Θ, little-o and little-ω, growth-order puzzles, and sums. The core route is Sections 1 and 3–6, then Practices 1–2: a simple explicit O bound, growth families, input cases, and time versus memory. Section 2’s strict notation and cubic proof, Section 7, and Practice 3 are optional second-pass extensions, not prerequisites for Week 9. Review C contains the longer scheduled review session.

Türkçe: Big-O bir üst sınırdır. “En fazla bu biçimde büyür” der; “tam olarak böyle büyür” demez. Hangi durumun maliyetini, hangi işlem modeliyle ve hangi girdi büyüklüğüne göre sınırladığımızı açıkça belirtmeliyiz.

Prerequisite warm-up, with answers

1. Simplify 7n+300 for growth. Answer: its dominant term is linear. Keep the full expression when calculating a particular count.
2. Is 5n ≤ 5n² for integer n ≥ 1? Answer: yes, because n ≤ n² on that domain.
3. Are two sequential n-step loops quadratic? Answer: no; n+n = 2n, a linear count.
4. What is the exact mean of comparison counts 1 through 1000? Answer: (1+1000)/2 = 500.5, not exactly 500.
5. Does a function returning a copied list need extra storage? Answer: yes; a copy of n references occupies space proportional to n under the usual model.

1. Read the definition one part at a time

For nonnegative costs, write T(n) = O(g(n)) when there are constants c > 0 and n₀ such that:

T(n) ≤ c × g(n) for every n ≥ n₀.

T is the cost we are bounding. g is the comparison function, such as n or n². The multiplier c may be generous but must be fixed: it cannot secretly change with n. The starting size n₀ lets a finite initial part behave differently. The phrase for every n ≥ n₀ is essential. Checking three large examples is not the same as proving the inequality thereafter.

Worked example 1 — exhibit a complete upper bound

Let T(n) = 7n+300. We want a bound proportional to n. Choose c = 10 and n₀ = 100.

For every n ≥ 100, multiplying the inequality n ≥ 100 by 3 gives 3n ≥ 300. Therefore:

T(n) = 7n + 300
     ≤ 7n + 3n
     = 10n.

We have justified the same constants for every n ≥ 100, so T(n) = O(n). These are not the only valid constants. For n ≥ 1, 300 ≤ 300n gives T(n) ≤ 307n, so c = 307 and n₀ = 1 also work. A proof needs one valid pair, not the smallest possible pair.

This cost is also O(n²), since n ≤ n² for n ≥ 1. That looser upper bound is true but less informative. This is why “O(n²)” alone cannot establish a quadratic doubling ratio or rule out linear behavior on every input.

Türkçe: c ve n₀ birer kanıt tanığıdır. c’yi n’ye bağlı seçemeyiz. Tek bir n’de eşitsizliğin doğru olması yetmez; seçtiğimiz başlangıçtan sonraki bütün n değerleri için gerekçe gerekir.

2. Optional second pass — upper, lower, tight, and strict relationships

The ratio descriptions assume positive comparison functions and the stated limits exist. Θ means growth within constant factors, not numerical equality. Since 3n/n = 3, 3n = Θ(n), but 3n is neither o(n) nor ω(n). A smaller coefficient is not a strictly smaller asymptotic order.

A lower bound on one algorithm's running time is also different from a lower bound on the problem. To show every correct algorithm must read n inputs in a worst case requires an argument about necessary information, not merely counting one implementation's loop.

Worked example 2 — prove a tight cubic bound

Let f(n) = n³−3n²−n+1. For n ≥ 10, divide by the positive quantity n³:

f(n)/n³ = 1 − 3/n − 1/n² + 1/n³.

Since 3/n ≤ 0.3 and 1/n² ≤ 0.01, discarding the positive last term gives f(n)/n³ ≥ 1−0.3−0.01 = 0.69 ≥ 0.5. Also −3n²−n+1 ≤ 0 for n ≥ 1, so f(n) ≤ n³. Thus, for every n ≥ 10:

0.5n³ ≤ f(n) ≤ 1n³.

We have c₁ = 0.5, c₂ = 1, and n₀ = 10, establishing Θ(n³). At n = 10, f(10) = 1000−300−10+1 = 691, between 500 and 1000. That numerical check illustrates the already-established inequalities; it is not their proof.

3. Growth families and what their labels do not promise

For positive fixed exponents and fixed exponential bases greater than one, the familiar eventual ordering is:

1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < 3ⁿ < n!

Here < describes eventually slower growth, not an inequality that must hold at every tiny n. Logarithm bases differ by a constant factor: log₂n = ln(n)/ln(2). Exponential bases are different: 3ⁿ/2ⁿ = (3/2)ⁿ grows without bound, so 3ⁿ is not O(2ⁿ).

For an exact model T(n) = cn², quadrupling n multiplies T by 16. For a mere upper bound T(n) = O(n²), that precise prediction is not justified. To estimate seconds, state a model fitted to a measured range and assume relevant conditions stay comparable. O notation does not provide its coefficient.

Likewise, 2ⁿ doubles when n increases by one. When n doubles, 2²ⁿ = (2ⁿ)². Under an illustrative machine model of ten million unit operations per second, n = 1,000,000 linear steps take 0.1 s; n² steps take 100,000 s, approximately 27.8 hours. These are unit-operation estimates, not real benchmark results.

4. Analyze the code's actual work

For statements in sequence, add costs. For nested loops, add each iteration's body cost; multiplication is the shortcut when a common bound applies. Do not decide solely by counting loop keywords.

The original report function combines these regions. Its total is O(1)+O(n)+O(n²)+O(n log n), hence O(n²). If the inner pair loop is limited to a fixed ten valid indices, that region becomes O(n); sorting becomes the dominant upper bound. Use range(min(10, n)) if the data can contain fewer than ten items.

Hidden work matters. Membership x in a_list may scan the list. Inserting at the front shifts references. Copying a list or taking a slice of length k costs O(k). If a loop over n queries scans a separate list of m items, report O(nm); reduce to O(n²) only when both lengths are tied to n.

5. State best, worst, and average cases explicitly

Big-O can bound a best-case, worst-case, or average-case function. It does not inherently mean worst case. This course often discusses worst-case guarantees, but the case should still be named.

For linear search in a nonempty list of n items, counting equality tests:

The average follows from adding 1+2+…+n = n(n+1)/2, then dividing by n equally likely positions. If absence is possible, or target positions are not equally likely, this model changes. “Average n/2” without a distribution is incomplete.

def search_count(data, target):
    comparisons = 0
    for item in data:
        comparisons += 1
        if item == target:
            return True, comparisons
    return False, comparisons

data = [10, 20, 30, 40]
for target in [10, 40, 99]:
    print(target, search_count(data, target))
assert search_count(data, 10) == (True, 1)
assert search_count(data, 99) == (False, 4)
assert search_count([], 99) == (False, 0)

The worst-case count is Θ(n) and the nonempty best case Θ(1). A Θ(n²) worst case can coexist with fast special inputs, but cannot coexist with a uniform O(n) bound over all inputs of each size.

Türkçe: Ortalama durum için olasılık varsayımı gerekir. Aranan öğe her konumda eşit olasılıkla bulunuyorsa ortalama (n+1)/2 olur. Big-O sembolü tek başına “en kötü durum” kelimelerini içermez; durumu ayrıca yazmalıyız.

6. Time and extra space are different accounts

Extra, or auxiliary, space excludes the input supplied to the algorithm. State whether returned output is included in your accounting. A scan keeping a total uses O(n) time and O(1) auxiliary variables. Building every ordered pair creates n² output items, so output space itself is Θ(n²).

An in-place reverse swaps endpoints inward. Its time is Θ(n), auxiliary space O(1), and it mutates the input. A reverse made by appending items in backward index order also takes Θ(n) time, but creates an O(n) result and preserves the original.

data = [1, 2, 3, 4]
reversed_copy = []
for index in range(len(data) - 1, -1, -1):
    reversed_copy.append(data[index])
assert reversed_copy == [4, 3, 2, 1]
assert data == [1, 2, 3, 4]
print(data, reversed_copy)

The original lesson's alternative result = [x] + result has the same O(n) peak result size but repeatedly copies the growing prefix. Its time is quadratic: approximately 1+2+…+n copied positions. Equal output and space requirements do not imply equal time. Also, an in-place function without return returns None, even though its input list has been reversed successfully.

7. Optional deepening — after the core check: chapter proof toolkit

Bound each lower-order term

For n ≥ 1, every power nⁱ with i ≤ k is at most nᵏ. A polynomial's absolute value is therefore at most (sum of absolute coefficients) × nᵏ. The coefficient sum is a constant. This supplies a general O(nᵏ) proof and handles negative coefficients safely.

For f = n√n+n² and g = n², n√n ≤ n² when n ≥ 1, so f ≤ 2g. For f = n²−n+1 and g = n²/2, the lower terms are nonpositive once n ≥ 1, so f ≤ n² = 2g. These are explicit witnesses, not only dominant-term labels.

Combine bounds with a shared starting point

If f₁ ≤ c₁g₁ after n₁ and f₂ ≤ c₂g₂ after n₂, use n₀ = max(n₁,n₂). For nonnegative functions, adding gives f₁+f₂ ≤ max(c₁,c₂)(g₁+g₂). Multiplying gives f₁f₂ ≤ c₁c₂g₁g₂. Lower-bound versions use the same idea; for sums choose the smaller positive lower multiplier.

Understand sums before simplifying

For log(n!), upper-bound each log i by log n: total ≤ n log n. At least the last n/2 terms have i ≥ n/2, giving a lower bound near (n/2)log(n/2). Together these establish Θ(n log n). Taking logs of the geometric sum 2ⁿ⁺¹−1 instead gives Θ(n).

For positive powers, summing iᵏ up to n gives Θ(nᵏ⁺¹). Do not apply “n times the largest term” indiscriminately: a geometric sum is Θ(its last term), and a harmonic sum behaves differently again.

Distinguish constants, bases, and variable exponents

Expressions 2ⁿ⁻¹, 2ⁿ and 2ⁿ⁺¹ differ only by fixed factors, so share a Θ class. Expressions 2ⁿ and 3ⁿ do not. (1/3)ⁿ shrinks toward zero, while a constant such as 6 stays fixed. For a fixed shift a and positive fixed exponent b, (n+a)ᵇ = Θ(nᵇ) once n is sufficiently large that the base is positive.

For variable exponents, take logs carefully. log₂(n^(log₂n)) = (log₂n)², whereas log₂(n log₂n) = log₂n + log₂log₂n. Parentheses change the function. Both are eventually below log₂((log₂n)^n) = n log₂log₂n, but they are not the same expression.

The source’s second ordering puzzle compares the sum √1+…+√n, the polynomial 12n³ᐟ²+4n, n^(√log₂n), and (√n)^(log₂n). The first two tie at Θ(n³ᐟ²). Set L = log₂n. The variable exponents of the last two are √L and L/2. Both eventually exceed the fixed exponent 3/2, and L/2 exceeds √L once L > 4. Thus the tied pair grows slowest, then n^(√log₂n), then (√n)^(log₂n). The ties describe growth, not equal numeric values.

Some pairs are not eventually comparable. If B(n) = n^(cos(πn/8)), then along n = 16k its value is n, while along n = 8+16k its value is 1/n. Against A(n) = √n, the ratio alternates between tending toward zero and growing without bound along these subsequences. Neither an eventual O nor Ω relationship holds. A single growth ladder does not cover every oscillating function.

8. Graduated practice with complete solutions

Practice 1 — provide constants, not just a label

Show 3n²+2n+5 = O(n²) for integer n ≥ 1. Give c and n₀.

Solution 1

Since n ≤ n² and 1 ≤ n², the expression is at most 3n²+2n²+5n² = 10n². Thus c = 10 and n₀ = 1 work. It is also Ω(n²) because the nonnegative extra terms leave it at least 3n², so it is Θ(n²).

Practice 2 — reveal hidden work and memory

A function starts an empty list seen, scans n input values, and appends a value only if it is not already in seen. Give worst-case time and space, and identify a contrasting easy input.

Solution 2

When every input is distinct, the membership scans inspect 0, 1, …, n−1 stored items. Total comparisons are n(n−1)/2, giving Θ(n²) worst-case time. The result grows to n items, giving O(n) extra space. When all values are equal, seen stays length one, and after the first insertion each membership check succeeds immediately: Θ(n) time and O(1) result size for that particular family. The case and storage convention must accompany the labels.

Practice 3 — optional challenge: order four functions and explain the sum

Order n²log₂n, n(log₂n)², the sum 1+2+4+…+2ⁿ, and the log₂ of that sum. Mark any ties.

Solution 3

The sum equals 2ⁿ⁺¹−1, so it has exponential growth. Its base-2 logarithm lies between n and n+1 for n ≥ 1, so it is Θ(n). Compare n(log₂n)² with n²log₂n by dividing both by positive n log₂n: the remaining comparison is log₂n versus n. The ordering is:

log₂(1+2+4+…+2ⁿ) < n(log₂n)² < n²log₂n < 1+2+4+…+2ⁿ.

There are no ties among these four growth rates. The reasoning uses identities and eventual comparisons, not a few numerical samples.

Misconceptions to repair

• “O(n²) means exactly quadratic.” An upper bound can be loose; a linear function also satisfies it.
• “Big-O always means worst case.” The symbol specifies a bound; name the case and, for averages, the distribution.
• “Linear memory implies linear time.” The copying-reversal example keeps only linear peak storage while repeatedly doing growing copies.

Glossary and readiness

You are ready when you can exhibit c and n₀, explain why O(n²) can be loose, calculate the successful-search mean, and give separate time and space accounts. If a bound feels like a guess, redo Practice 1 using inequalities. If you mix cases, write three separate rows for search. Use Review C to repair those core gaps. Strict small-o/omega, oscillation examples, and extended function ordering are optional: when returning to them, simplify powers, logs, and sums before comparing. They need not be mastered before Week 9.

Bridge to Week 9: four correct anagram methods will apply these distinctions. You will compare strategy, operation counts, input contracts, hidden built-in work and memory rather than choosing a winner from a complexity label alone.

Big-O describes a limit on growth

Big-O gives an upper bound: for large enough inputs, the work stays below a fixed multiple of the named growth pattern. Say what work you are counting. Big-O does not give seconds, an exact count, or necessarily the closest bound. Best and worst cases describe which inputs you consider.

Draw or trace. Compare T(n) = 3n + 2 with the upper limit 5n for n ≥ 1. Show why every value of the first expression stays under the second for those input sizes.

Predict before checking. Is 3n + 2 also O(n squared)? If so, does that mean its actual growth is quadratic?

Worked reasoning

For n ≥ 1, 3n + 2 ≤ 5n ≤ 5n squared. So both O(n) and O(n squared) are valid upper bounds. Θ(n), read “theta of n”, says the growth is linear from both above and below. Checking a few values helps us see the pattern; the algebra shows it holds for every n ≥ 1. When counting memory, say whether you include the input or only the extra storage, called auxiliary memory.

for n in (1, 2, 10, 100):
    assert 3 * n + 2 <= 5 * n <= 5 * n * n
print("Sample checks illustrate the algebraic bound; they do not prove it alone.")

Change one thing. Compare a scan that stops at the first match with the same scan for a missing target. Keep the algorithm fixed and change the input case.

Türkçe: Big-O üst sınırdır; süre ölçümü veya zorunlu olarak sıkı sınır değildir. Durumu, maliyet modelini ve yardımcı belleği ayrıca belirt.

Additional analysis laboratory

Big-O should not arrive as a magic label. Require a witness or a reason. For beginner work, a plain-language witness is often enough: give a constant multiplier and a starting size, or point to a known operation with stated assumptions.

Extra exam-style prompt: Show that 8n + 50 = O(n). Give valid constants.

Solution: For n >= 1, 50 <= 50n. Therefore 8n + 50 <= 58n. So c = 58 and n0 = 1 work. A tighter choice is possible, but unnecessary. The expression is also O(n^2), but O(n) is the closer useful bound.

Turkce: Big-O cikarimi "bence" ile bitmez. Bir esitsizlik, bir dongu sayimi veya belgelenmis bir veri yapisi modeli gerekir.