# Complexity and efficiency basics

Physics I · Computer Science · https://tryals.app/learn/physics-i/complexity-and-efficiency-basics

## Big-O Notation

**Big-O notation** describes how an algorithm's run time scales with input size $n$.

| Big-O | Name | Example |
| --- | --- | --- |
| $O(1)$ | Constant | Array index 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 | Brute-force subsets |

**Space complexity** measures memory usage by this exact same logic.

## Scaling and Pitfalls

To determine complexity: single loop is $O(n)$, nested loop is $O(n^2)$, and halving the input is $O(\log n)$.

**Practical example:** Computing pairwise distances between $n$ particles uses nested loops, yielding $O(n^2)$. Advanced methods like **Barnes-Hut** reduce this to $O(n\log n)$ using spatial trees.

**Common pitfall:** Big-O hides constants. An $O(n^2)$ method can beat an $O(n\log n)$ one on small inputs. Complexity classes predict **scaling**, not micro-benchmarks.

## Practice questions

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

### 1. $O(n^2)$ simplifies to $O(n)$ in Big-O notation, since constant factors are dropped.

**Answer:** False

**Why:** False. Big-O drops constant *multipliers*, so $O(2n) = O(n)$, but $n^2$ is a different growth class entirely and never reduces to $n$. Confusing a coefficient with an exponent is the single most common Big-O error, and it changes the answer by orders of magnitude at scale.

Page: https://tryals.app/practice/physics-i/complexity-and-efficiency-basics/o-n-simplifies-to-o-n-in-big-o-notation-since-constant-factors

### 2. An $O(n^2)$ algorithm can beat an $O(n\log n)$ one on real data. How is that consistent with the complexity classes?

A. Because the $O(n^2)$ algorithm must have been implemented in a faster language
B. Because big-O describes growth and discards constants
C. Because complexity analysis is only a rough guide and is often wrong
D. Because $O$ notation describes the best case rather than the worst

**Answer:** B. Because big-O describes growth and discards constants

**Why:** Asymptotic notation is about the limit, and real inputs are finite. Timsort and introsort both exploit this by switching algorithms below a size threshold.

Page: https://tryals.app/practice/physics-i/complexity-and-efficiency-basics/an-o-n-algorithm-can-beat-an-o-nlog-n-one-on-real-data-how-is

### 3. Two nested loops each running $n$ times give $O(n^{2})$. Why does the analysis not simply add the two loops?

A. Because the inner loop runs in full for EACH outer iteration
B. Because the outer loop variable is reused inside the inner loop
C. Because big-O never permits addition of terms
D. Because nested loops are always slower than sequential ones by a constant factor

**Answer:** A. Because the inner loop runs in full for EACH outer iteration

**Why:** Nesting multiplies, sequencing adds. Two sequential $n$-loops are $O(n)$; two nested ones are $O(n^{2})$, and the code looks almost identical.

Page: https://tryals.app/practice/physics-i/complexity-and-efficiency-basics/two-nested-loops-each-running-n-times-give-o-n-why-does-the

### 4. Match each everyday task to the growth rate of its work as $n$ grows.

**Answer:**

- Finding a page number in a book’s index → $O(\log n)$
- Reading every page of a book once → $O(n)$
- Comparing every page with every other page → $O(n^{2})$
- Opening the book’s front cover → $O(1)$

**Why:** Big-O is the "what happens when n doubles" question: $O(1)$ shrugs, $O(\log n)$ adds one step, $O(n)$ doubles, $O(n^{2})$ quadruples. Growth class, not raw speed, decides what is feasible at scale.

Page: https://tryals.app/practice/physics-i/complexity-and-efficiency-basics/match-each-everyday-task-to-the-growth-rate-of-its-work-as-n-grows

### 5. An $O(n^{2})$ simulation takes **2 seconds** for $n = 1000$ particles. Predict its runtime for $n = 5000$, in seconds.

**Answer:** 50 (within ±5)

**Why:** $2 \times 25 = 50$ s. Extrapolating by growth class is a superpower: before buying hardware, you know 50,000 particles would take ~83 minutes, and that an $O(n\log n)$ algorithm is worth finding.

Page: https://tryals.app/practice/physics-i/complexity-and-efficiency-basics/an-o-n-simulation-takes-2-seconds-for-n-1000-particles-predict