# Complexity and Performance Trade-offs

Computer Science I · Programming II · https://tryals.app/learn/computer-science-i/complexity-and-performance-trade-offs

## How an Algorithm Scales

Two programs can both be correct yet differ wildly in speed as data grows. **Complexity analysis** measures how an algorithm's cost grows with **input size** $n$, ignoring hardware constants to focus on the growth shape.

**Big-O notation** expresses an upper bound on that growth. For large $n$, growth classes dominate all constants; an $O(n \log n)$ sort beats $O(n^2)$ regardless of tuning.

| Big-O | Name | Example |
| --- | --- | --- |
| $O(1)$ | Constant | Array index access |
| $O(\log n)$ | Logarithmic | Binary search (halving step) |
| $O(n)$ | Linear | Scanning a list once |
| $O(n \log n)$ | Linearithmic | Efficient sorting |
| $O(n^2)$ | Quadratic | Nested loops over data |
| $O(2^n)$ | Exponential | Trying all subsets |

## Trade-offs and Pitfalls

Performance involves choices beyond raw loops. The **space-time trade-off** lets you spend more memory to save time, such as using a lookup table.

An algorithm also has **best**, **average**, and **worst** cases. Big-O usually describes the worst case unless specified otherwise.

$$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)$$

> **Common pitfall:** Judging performance on _small_ inputs where constant factors dominate. An $O(n^2)$ algorithm can beat an $O(n \log n)$ one on tiny inputs, yet lose catastrophically as $n$ scales.

## Practice questions

5 of this lesson's 11 practice questions, with answers. The full set is in the app.

### 1. Two algorithms are timed on one machine: the O(n) one takes 3 seconds at n = 1000 and the O(n²) one takes 1 second. What can you predict about n = 100,000, and what can you not?

A. That a crossover exists and roughly where, but not the exact times.
B. Nothing can be predicted, since big-O says nothing about actual running times.
C. The quadratic algorithm will remain faster, since it started faster.
D. Both times can be computed exactly by multiplying by the growth factor.

**Answer:** A. That a crossover exists and roughly where, but not the exact times.

**Why:** Scaling n by 100 multiplies linear work by 100 and quadratic by 10,000, so 3 seconds becomes 300 and 1 second becomes nearly three hours, the initial advantage is irrelevant at scale. What growth classes cannot give you is the actual numbers, and at large n the quadratic may exceed memory and start swapping, at which point the extrapolation understates the disaster.

Page: https://tryals.app/practice/computer-science-i/complexity-and-performance-trade-offs/two-algorithms-are-timed-on-one-machine-the-o-n-one-takes-3-seconds

### 2. An O(n log n) sort applied to a nearly-sorted list can be slower than an O(n²) insertion sort on the same data. Why does the input's shape overturn the growth classes?

A. Because insertion sort changes its growth class when the data is sorted, which is unusual among algorithms.
B. Because O(n²) is its worst case, and nearly-sorted data approaches O(n).
C. Because nearly-sorted lists are shorter than random ones on average.
D. Because O(n log n) sorts have larger constant factors in every situation.

**Answer:** B. Because O(n²) is its worst case, and nearly-sorted data approaches O(n).

**Why:** Insertion sort's quadratic figure is its *worst* case: on sorted data each element is compared once and stays put, where merge sort does its full work regardless of input. So the comparison depends on which case the input puts you in. Quicksort is the mirror image, quadratic on sorted input with a naive pivot, and Timsort detects existing runs precisely to claim insertion sort's best case.

Page: https://tryals.app/practice/computer-science-i/complexity-and-performance-trade-offs/an-o-n-log-n-sort-applied-to-a-nearly-sorted-list-can-be-slower-than

### 3. Order these growth classes from the slowest-growing to the fastest-growing as n becomes large.

**Answer:**

1. Constant
2. Logarithmic
3. Linear
4. Linearithmic
5. Quadratic
6. Exponential

**Why:** The order is constant, logarithmic, linear, linearithmic, quadratic, exponential. Linearithmic is only a logarithm worse than linear, which is why a good sort stays practical on huge inputs while a quadratic sort does not, and why exponential algorithms become impossible at input sizes the others handle easily.

Page: https://tryals.app/practice/computer-science-i/complexity-and-performance-trade-offs/order-these-growth-classes-from-the-slowest-growing-to-the

### 4. A team spends a week optimising a function that accounts for 2% of runtime. What did they get, and what is the rule they violated?

A. An improvement that cannot be predicted without benchmarking afterwards
B. A 2% improvement, which is a reasonable return for a week
C. Nothing, since micro-optimisations never produce measurable gains
D. At most a 2% improvement, since the other 98% dominates

**Answer:** D. At most a 2% improvement, since the other 98% dominates

**Why:** Making 2% of the runtime instantaneous saves 2%, so the ceiling was set before they started. Profiling first is the discipline, and the reason it matters is that developers guess hot spots badly, which is why 'measure, don't guess' outranks any particular optimisation technique.

Page: https://tryals.app/practice/computer-science-i/complexity-and-performance-trade-offs/a-team-spends-a-week-optimising-a-function-that-accounts-for-2-of

### 5. Big-O notation compares how algorithms scale, so an $O(n\log n)$ algorithm always runs faster than an $O(n^{2})$ one on the same input.

**Answer:** False

**Why:** False. Big-O describes growth as n tends to infinity and discards constant factors, so a heavily-optimised $O(n^{2})$ routine can beat a constant-heavy $O(n\log n)$ one at every n a real program ever sees. The crossover point is a measurement, not something the notation tells you.

Page: https://tryals.app/practice/computer-science-i/complexity-and-performance-trade-offs/big-o-notation-compares-how-algorithms-scale-so-an-o-nlog-n