Unit 1.1 · about 4 h
88 / 324Cost models, asymptotic notation and cases
Every later choice in this stage starts by reading the constraint line. A wrong budget rejects a working algorithm before it is written, or accepts one that cannot finish.
- explain
- derive
You can now
- Translate an input bound into a cost budget: state which complexity classes fit \(n\) up to 5000, \(10^5\) and \(10^9\).
- Define Big-O, Big-Omega and Big-Theta with quantifiers, and prove a polynomial bound such as \(100x^2 = O(x^2)\) from the definition.
- Derive time and auxiliary-space bounds for nested and input-dependent loops, naming the variable each bound is in.
Covers
- Input size, operation model and resource budget
- Big \(O\), \(\Theta\) and \(\Omega\) with stated variables
- Worst, average, expected and output-sensitive cost
Study, in this order
4 steps
- Computational complexity and Big-ODSA Handbook - Foundations and linear patterns
What complexity actually means; How to read a complexity bound (the five notations); The hierarchy you will meet with the input-size table; Space-time tradeoffs
- Mathematics for Computer Science, Chapter 13, Section 13.7MIT 6.042J - asymptotics and invariants
Section 13.7 Asymptotic Notation (printed pp. 528 to 549): 13.7.1 Little O, 13.7.2 Big O with Definitions 13.7.5 and 13.7.9 plus Proposition 13.7.10 (\(100x^2 = O(x^2)\)), 13.7.3 \(\Theta\) with Definition 13.7.13, 13.7.4 Pitfalls, 13.7.5 \(\Omega\) with Definitions 13.7.15 and 13.7.16
- Complexity ModelsAlgorithmica - memory and data layout
Classical Complexity Theory and Asymptotic Complexity: the instruction-count model and where it breaks (clock speeds and instruction latencies)
- Programming Languages and constant factorsAlgorithmica - memory and data layout
Interpreted languages, Compiled Languages and Takeaway: the pure-Python versus C versus OpenBLAS matrix-multiply comparison
Depth · Read for the constant-factor warning only. Algorithmica's timings are C++ measurements; do not carry any crossover point to Python without your own
timeitrun.
Focus on
- Constraints are budgets: \(n\) up to 10 admits \(O(n!)\) brute force, \(n\) up to \(10^5\) admits \(O(n \log n)\) or better, and a value \(n\) up to \(10^9\) admits only \(O(\sqrt{n})\), \(O(\log n)\), a closed form or a lookup.
- The equality in \(f(n) = O(g(n))\) is one-way: \(n = O(n^2)\) holds and the reverse is nonsense.
- Worst case is the default reading of complexity; average, expected and amortized each need their own argument, supplied by later units.
- Constants are invisible in the notation: the handbook plans Python at about \(10^7\) simple ops per second against \(10^8\) for compiled languages.
Reproduce closed-book
Traps
- Reading Big-O as an exact operation count. It bounds growth up to a constant, and the constant decides close races.
- Quoting the handbook's operations-per-second rates, its \(n = 50\) sort crossover or its ten-to-thirty-second estimate for scanning \(10^9\) items as measured facts. They are rough compiled-language planning numbers; time your own code with
timeitbefore repeating them. - Calling one fast observed run an average case. A single input is one sample; an average needs a stated distribution.
Practice
Implement the \(O(n^2)\) brute-force double loop and the \(O(n)\) complement hashmap. Time both with timeit at \(n = 2000\), seed 0, target absent: expect about 0.05 s per brute run against about 0.1 ms per hash run. State both bounds with the named variable \(n\).
After submitting, read the handbook hash-maps section LC 1: value-to-index map for the lookup-then-insert order that avoids matching an element with itself on inputs like [3, 3].
Self-test
-
Prove \(100x^2 = O(x^2)\) from the definition.
Take \(c = 100\) and \(x_0 = 1\). For all \(x \ge 1\), \(0 \le 100x^2 \le 100 \cdot x^2\). This is Proposition 13.7.10. -
\(n = O(n^2)\) is true. Is \(n^2 = O(n)\)?
No. For every fixed \(c\), \(n^2 > c \cdot n\) once \(n > c\), so no constant works. The equality reads one way only. -
A problem allows \(n\) up to \(10^9\) on a one-second budget. Why is a linear scan rejected before coding?
At the planning rate of about \(10^8\) simple operations per second for compiled code, \(10^9\) steps take about 10 s, and Python at about \(10^7\) per second needs over a minute. An input that large is usually one number, not an array, so \(O(\sqrt{n})\) (about \(3 \times 10^4\) steps), \(O(\log n)\), a closed form or a lookup fits. -
A dynamic-array push is \(O(1)\) amortized. Does that bound the slowest single push?
No. The push that triggers a resize copies every element, which is \(O(n)\). Amortized averages over the sequence; latency-critical code cannot use the average.
Completion criterion
Stop when
You prove a polynomial \(\Theta\) bound from the definitions without notes, and your Two Sum timing shows the predicted gap with both bounds stated.
Mark passed, then open 1.2 Only mark this when you can do it without notes.Leads to
- 1.2 Aggregate, accounting and potential amortized analysis Amortized bounds reuse the same definitions with the average taken over a sequence.
- 1.4 Arrays, strings, locality and linked structures Arrays are the first structure whose operations you cost with this vocabulary.
Comes after
- 1.1 Proof habits and shape notationApply quantifier discipline to asymptotic bounds.
Resources for this unit
- DSA Handbook - Foundations and linear patterns Study Part 0, Part 1, Part 3 and Part 4 in order, plus the Part 5 Linked-list fundamentals chapter. Use the routing-rule pages for arrays versus lists, map choice, stack versus queue, two pointers, sliding windows and prefix methods before seeing solved code.
- MIT 6.042J - asymptotics and invariants Use the asymptotics, state-machine invariants and proof-method readings when a cost or correctness argument is weak. Solve only the matching problems.
- Algorithmica - memory and data layout Read the memory hierarchy, cache and complexity-model chapters, then measure one contiguous-versus-linked and one hash-versus-ordered workload crossover.
Also in this section
- AlgoMaster DSA - linear structures slice Attempt Design HashMap, Longest Substring Without Repeating Characters and Sliding Window Maximum cold. Hide tags, state the invariant first, and add randomized operation histories to Design HashMap.
- Algorithms lecture notes - amortized analysis and hashing Use note 9 Amortized Analysis for the summation, taxation, charging and potential-function proofs, and note 5 Hashing for chaining, universal hashing and open-addressing analysis, when the handbook treatment is too brief for a proof.
- NeetCode - unseen linear problems Use only for two tag-hidden transfer problems after the AlgoMaster slice. Do not start another full roadmap or watch a solution before the attempt is complete.
- Hypothesis documentation - Quickstart and stateful testing Follow Quickstart for
@givenstrategies and the pytest combination, Configuring test settings formax_examplesandderandomize, then Rule-based state machines (rule,precondition,invariant,run_state_machine_as_test) for randomized operation histories againstdictanddequeoracles. - CPython source - list and dict objects Read
list_resizeinObjects/listobject.cfor the growth formula and pattern comment, and theUSABLE_FRACTIONdefinition, perturbation-probing comment and dummy-entry handling inObjects/dictobject.c. Read the cited functions and comments only.