# Computational Complexity

Mathematics I · Programming Elements · https://tryals.app/learn/mathematics-i/computational-complexity

## Scaling & Big-O Notation

Two algorithms solve the same problem, but one finishes instantly while the other takes centuries. **Computational complexity** measures how an algorithm's resource use—usually **time** (number of basic steps)—grows as input size $n$ grows.

We describe this growth using **big-O notation**, which captures the **dominant term** and drops constants and lower-order terms. For large $n$, only the fastest-growing part matters.

| Complexity | Name | Example |
| --- | --- | --- |
| $O(1)$ | **constant** | indexed array access |
| $O(\log n)$ | **logarithmic** | binary search |
| $O(n)$ | **linear** | single loop |
| $O(n \log n)$ | **linearithmic** | merge sort |
| $O(n^2)$ | **quadratic** | nested loops |
| $O(2^n)$ | **exponential** | doubling per element |

## The Asymptotic Gulf

The gulf between complexity classes is enormous. For $n = 1{,}000{,}000$, a linear algorithm takes a million steps while a quadratic one takes a trillion—seconds versus weeks.

Big-O describes **asymptotic** behavior ($n \to \infty$), so $O(n)$ and $O(100n)$ are the same class. Choosing the right algorithm matters far more than machine speed.

> **Common pitfall:** Confusing an algorithm's **complexity class** (its scaling trend) with its **raw speed on small inputs**. Big-O drops constants. A quadratic algorithm might beat a linear one on tiny inputs, but $O(n)$ is guaranteed to win once $n$ is large enough.

## Practice questions

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

### 1. Select every statement about big-O notation that is TRUE.

A. The dominant term determines the class
B. Big-O reports the exact number of seconds an algorithm takes
C. Halving the remaining problem at each step gives logarithmic growth
D. For large n, a linearithmic sort scales better than a quadratic one
E. Big-O keeps constants, so O(n) and O(100n) are different classes

**Answer:** A. The dominant term determines the class; C. Halving the remaining problem at each step gives logarithmic growth; D. For large n, a linearithmic sort scales better than a quadratic one

**Why:** Big-O drops constants and lower-order terms and describes growth, not wall-clock time; the other three statements are exact. Wanting big-O to predict seconds is the commonest misreading of it.

Page: https://tryals.app/practice/mathematics-i/computational-complexity/select-every-statement-about-big-o-notation-that-is-true

### 2. Match each complexity class to an operation that has it.

**Answer:**

- Constant → Indexed access to one array element
- Logarithmic → Binary search on sorted data
- Linearithmic → Merge sort
- Quadratic → Two nested loops over the same data

**Why:** These four examples are the canonical ones, and they are worth memorising because almost every algorithm you meet resembles one of them. Merge sort's linearithmic cost is the best any comparison-based sort can achieve.

Page: https://tryals.app/practice/mathematics-i/computational-complexity/match-each-complexity-class-to-an-operation-that-has-it

### 3. Order these complexity classes from the slowest-growing to the fastest-growing.

**Answer:**

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

**Why:** Constant, logarithmic, linear, quadratic, exponential is the standard ladder. The gaps are enormous: at n = 1,000,000 the linear algorithm does a million steps and the quadratic a trillion, while the exponential one is hopeless well before n = 100.

Page: https://tryals.app/practice/mathematics-i/computational-complexity/order-these-complexity-classes-from-the-slowest-growing-to-the

### 4. A quadratic algorithm takes 4 seconds on an input of size 1000. Assuming the quadratic model holds, roughly how many seconds does it take on an input of size 3000?

**Answer:** 36

**Why:** Tripling n multiplies quadratic work by 9, so 4 seconds becomes 36. Note that the constant factor never had to be known, that is exactly the information big-O throws away and still predicts correctly.

Page: https://tryals.app/practice/mathematics-i/computational-complexity/a-quadratic-algorithm-takes-4-seconds-on-an-input-of-size-1000

### 5. Binary search halves the remaining portion of a sorted list at each step. Starting from 1024 items, how many halvings reduce it to a single item?

**Answer:** 10

**Why:** $2^{10} = 1024$, so ten halvings suffice. This is why logarithmic algorithms are so powerful: a thousandfold increase in data costs only ten extra steps.

Page: https://tryals.app/practice/mathematics-i/computational-complexity/binary-search-halves-the-remaining-portion-of-a-sorted-list-at-each

### 6. Binary search is O(log n) and needs sorted data; a linear scan is O(n) and needs nothing. For a list searched **once**, which wins?

A. They are equivalent, since both must examine the data at least once
B. The linear scan, since sorting first costs more than it saves
C. Binary search, because sorting is a one-off cost that is never counted
D. Binary search, since O(log n) always beats O(n)

**Answer:** B. The linear scan, since sorting first costs more than it saves

**Why:** Sorting to save one scan is a loss: O(n log n) to avoid O(n). The crossover comes at roughly log n searches, after which the preprocessing is repaid many times, which is the same calculation that decides whether a database should build an index or just scan the table.

Page: https://tryals.app/practice/mathematics-i/computational-complexity/binary-search-is-o-log-n-and-needs-sorted-data-a-linear-scan-is

### 7. Complete the description of big-O notation.

**Answer:** Big-O keeps only **the dominant term** because it describes behaviour as n grows without bound.

**Why:** For large n the fastest-growing term swamps everything else, so only it is kept. That is why 3n squared + 500n + 900 is simply quadratic, and why O(n) and O(100n) name the same class.

Page: https://tryals.app/practice/mathematics-i/computational-complexity/complete-the-description-of-big-o-notation

### 8. An O(n²) algorithm can beat an O(n log n) one on real data. Why does big-O notation not settle which program to use?

A. Because big-O is only an estimate, and exact operation counts would give a different ordering.
B. Because O(n²) is smaller than O(n log n) for all realistic input sizes.
C. Because big-O measures memory rather than time, so it does not bear on speed at all.
D. Because big-O describes growth and discards constant factors.

**Answer:** D. Because big-O describes growth and discards constant factors.

**Why:** Big-O discards constants and lower-order terms to answer one question cleanly, and those discarded parts decide small cases: at n = 10, 100·n log n is about 3300 units against 2n²'s 200. Production sorts are hybrids for exactly this reason, switching to insertion sort below 10 to 20 elements. The mistake is treating an answer about growth as an answer about speed.

Page: https://tryals.app/practice/mathematics-i/computational-complexity/an-o-n-algorithm-can-beat-an-o-n-log-n-one-on-real-data-why-does