🎓 A1Learner
🔍

DSA Stating Complexity Honestly

A complexity statement is a promise about how work grows as the input grows. An honest statement names which case the promise covers.

Worst and average in one search

A linear search counts its comparisons for three targets in one list. The first element costs one comparison, and the last costs ten.

def search_counts(nums, target):
    for i, x in enumerate(nums):
        if x == target:
            return i + 1
    return len(nums)

nums = list(range(10))
print("first element:", search_counts(nums, 0), "comparisons")
print("last element:", search_counts(nums, 9), "comparisons")
print("missing value:", search_counts(nums, 42), "comparisons")

Amortised appends, counted

A growing list doubles its capacity when it fills, copying the old cells. The copies look expensive, yet the total stays under three steps per append.

def append_costs(n):
    size = 0
    capacity = 0
    copies = 0
    writes = 0
    for _ in range(n):
        if size == capacity:
            capacity = max(1, capacity * 2)
            copies += size
        size += 1
        writes += 1
    return copies, writes

for n in [10, 100, 1000]:
    c, w = append_costs(n)
    print(n, "appends: copies", c, "+ writes", w, "= total", c + w)

What a hash promises on average

Six words land in four buckets under an arithmetic hash. The loads come out uneven, so the promise is about the average bucket, not every bucket.

def toy_hash(word, buckets):
    h = 0
    for ch in word:
        h = h * 31 + ord(ch)
    return h % buckets

words = ["ant", "bee", "cat", "dog", "elk", "fox"]
loads = [0] * 4
for w in words:
    loads[toy_hash(w, 4)] += 1
print("bucket loads:", loads)
print("average load:", len(words) / 4)
print("fullest bucket:", max(loads))

Example

def pair_checks(n):
    checks = 0
    for i in range(n):
        for j in range(i + 1, n):
            checks += 1
    return checks

print("claim 1: 'pair search is O(n)'")
for n in [10, 20, 40]:
    print("  n =", n, "checks:", pair_checks(n))
print("  verdict: doubling n multiplies the checks by about four -> O(n^2)")

def bad_hash(word):
    return len(word) % 4

words = ["ant", "bee", "cat", "dog", "elk", "fox"]
chain = {}
for w in words:
    chain.setdefault(bad_hash(w), []).append(w)

def probes(word):
    bucket = chain[bad_hash(word)]
    for i, w in enumerate(bucket):
        if w == word:
            return i + 1
    return len(bucket)

print("claim 2: 'hash lookup is always O(1)'")
print("  probes for the first word in its chain:", probes("ant"))
print("  probes for the last word in its chain:", probes("fox"))
print("  verdict: O(1) is the expected case, O(n) is the colliding worst case")

def append_costs(n):
    size = 0
    capacity = 0
    copies = 0
    writes = 0
    for _ in range(n):
        if size == capacity:
            capacity = max(1, capacity * 2)
            copies += size
        size += 1
        writes += 1
    return copies + writes

print("claim 3: 'appending costs O(n) every time'")
total = append_costs(100)
print("  100 appends cost", total, "steps in total")
print("  verdict: about two steps per append -> O(1) amortised is honest")

Key points

  • A complexity statement promises how work grows as input grows.
  • The worst case is the most work any input of that size can cause.
  • The average case is the mean work over many inputs of that size.
  • An amortised bound spreads one expensive step over many cheap steps.
  • Expected means averaged over the hash function's random choices, not guaranteed per call.
  • Space is counted in extra cells, the same way time is counted in steps.

In this example, three complexity statements from earlier solutions are audited with operation counts. The first claim called a pair search O(n). Its checks grew from 45 to 190 to 780 as n doubled, so the honest bound is O(n^2). The second claim called hash lookup always O(1). With a bad hash, all six words shared one chain, and the last word cost six probes. The honest statement is expected O(1) with an O(n) worst case. The third claim charged every append O(n). One hundred appends cost 227 steps in total, about two steps each. The honest statement is O(1) amortised. Space was counted the same way throughout. The pair search holds O(1) extra cells, and the hash table holds O(n).

Note

A claim without its case is only half a statement.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A lookup is described as expected O(1). What does the word expected promise?