# Complexity Analysis

Computer Science I · Algorithmics · https://tryals.app/learn/computer-science-i/complexity-analysis

## Measuring Cost Precisely

**Complexity analysis** predicts how an algorithm's **time** (operations) and **space** (memory) grow with input size $n$ without running code.

The tool is **asymptotic notation**, which ignores constants and lower-order terms to focus on scaling behavior for large inputs:

| Notation | Bound Type | Meaning |
| --- | --- | --- |
| **Big-O** ($O$) | Upper bound | Grows at most this fast |
| **Big-Omega** ($\Omega$) | Lower bound | Grows at least this fast |
| **Big-Theta** ($\Theta$) | Tight bound | Grows exactly this fast |

Count dominant operations: a loop is $O(n)$, nested loops are $O(n^2)$, halving is $O(\log n)$, and fixed work is $O(1)$.

**Common pitfall:** Writing '$O(3n^2 + 5n)$'. Drop constants and lower terms: it is simply $O(n^2)$, because the dominant term alone captures scale.

## Cases and Space

Costs depend heavily on **case**: the **worst case** bounds maximum slowness, the **average case** reflects typical inputs, and the **best case** is usually uninformative.

**Space complexity** measures memory. Algorithms often feature a space-time trade-off: merge sort takes $O(n \log n)$ time but $O(n)$ extra space, while heapsort sorts in place with $O(1)$ space.

**Quick Rules:**
- Only the fastest-growing term matters: $O(n^2 + n)$ simplifies to $O(n^2)$.
- Quicksort is $O(n \log n)$ average but $O(n^2)$ worst case.
- Always evaluate both time and memory constraints before selecting an algorithm for large datasets.

## Practice questions

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

### 1. Best case, average case and worst case give three different answers for the same algorithm. Which one should a system be designed around, and why?

A. The best case, since good engineering should aim at the achievable optimum.
B. It depends on the consequence of being slow.
C. Always the worst case, since it is the only rigorous bound.
D. Always the average case, since the worst case almost never occurs in practice.

**Answer:** B. It depends on the consequence of being slow.

**Why:** The right case depends on what a slow operation costs: a web server absorbs an occasional slow request, and a real-time system that misses a deadline has missed it. Which is why quicksort is a fine default and a poor real-time choice. The worst case is also an attack surface, hash flooding triggers it deliberately, and 'it never happens in practice' holds only while nobody is trying.

Page: https://tryals.app/practice/computer-science-i/complexity-analysis/best-case-average-case-and-worst-case-give-three-different-answers

### 2. Two algorithms are both O(n). One runs in 3n operations, the other in 3000n. Big-O calls them identical. Is the notation failing?

A. Yes, because two algorithms with different runtimes cannot share a class
B. Yes, the notation should include constants to be useful
C. No, because a thousandfold constant difference is negligible in practice
D. No, constants are discarded because they depend on the machine

**Answer:** D. No, constants are discarded because they depend on the machine

**Why:** The discard is deliberate: constants shift with hardware, compiler and cache while the growth rate does not, so big-O captures the portable part. It answers 'what happens as the input grows' and never claimed to answer 'which is faster today', that question is settled by measurement.

Page: https://tryals.app/practice/computer-science-i/complexity-analysis/two-algorithms-are-both-o-n-one-runs-in-3n-operations-the-other-in

### 3. Select every true statement about complexity analysis.

A. Constant factors are kept in a Big-O answer
B. Lower-order terms drop out, so n squared plus n is simply quadratic.
C. Quicksort is O(n log n) on average but O(n^2) in the worst case
D. Big-Theta is a tight bound
E. Space complexity measures how memory grows with input size

**Answer:** B. Lower-order terms drop out, so n squared plus n is simply quadratic.; C. Quicksort is O(n log n) on average but O(n^2) in the worst case; D. Big-Theta is a tight bound; E. Space complexity measures how memory grows with input size

**Why:** Dropping lower-order terms, tight bounds, quicksort's cases, and space complexity are all as taught. Keeping constant factors in a Big-O answer is exactly what the pitfall warns against.

Page: https://tryals.app/practice/computer-science-i/complexity-analysis/select-every-true-statement-about-complexity-analysis

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

**Answer:**

1. O(1)
2. O(log n)
3. O(n)
4. O(n log n)
5. O(n^2)

**Why:** From slowest to fastest growth: O(1), O(log n), O(n), O(n log n), O(n^2). Knowing this ordering is what lets you compare algorithms at a glance.

Page: https://tryals.app/practice/computer-science-i/complexity-analysis/order-these-complexity-classes-from-slowest-growing-to