Asymptotic analysis
Introduit| English | Sens |
|---|---|
| data structures and algorithms | data structures and algorithms |
| Big-O/bɪɡ əʊ/ | Big-O |
| Big-Θ | Big-Θ |
The yardstick
- Data structures and algorithms is choosing containers and recipes by what they cost as the input grows. Big-O bounds growth from above up to a constant; its lower-bound twin is Big-Ω; Big-Θ pins the exact rate.
- Drop constants and lower-order terms: $3n^2 + 5n + 7$ is $\Theta(n^2)$ — at $n = 1000$, $n \log_2 n \approx 9\,966$ against $n^2 = 10^6$: a factor of about $100$.
{exercise:uni-cs0501-classes}
The class of 3n^2 + 5n + 7 is —
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Drop constants and lower-order terms; the n squared term eats the rest.
The growth table
- At $n = 10 / 100 / 1000$: $\log_2 n$ reads $3 / 7 / 10$; $n \log_2 n$ reads $33 / 664 / 9\,966$; $n^2$ reads $100 / 10^4 / 10^6$; $2^{100} \approx 10^{30}$.
- Halving work is the source of logs: an algorithm that halves $n$ each step touches $\log_2 n$ levels — binary search on $16$ items makes at most $4$ probes because $2^4 = 16$.
{exercise:uni-cs0501-log}
Halving the input each step touches —
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Each halving is one step: 16 items resolve in 4 probes because 2 to the 4th is 16.
Measure by doubling
- Two loops over $n = 100$: the single loop runs its body $100$ times, the nested $100 \times 100 = 10\,000$. Double $n$: the linear body doubles to $200$, the nested quadruples to $40\,000$.
- The measured ratio on doubling is the exponent: $2$ means linear, $4$ means quadratic. Never trust a cost claim you have not counted.
A loop that halves i each pass is $\Theta(\log n)$; two sequential loops over $n$ add to $\Theta(n)$; a loop inside a halving loop multiplies to $\Theta(n \log n)$ — merge sort's shape.
{exercise:uni-cs0501-double}
Doubling n quadruples the running count. The exponent is —
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
The measured ratio on doubling is the exponent: 4 means quadratic.