# Time and Space Complexity — Part 1: Big-O Notation

## 1. What Big-O Measures

Big-O notation describes how an algorithm's running time (or memory use) **grows** as input size (`n`) grows — not the exact time in seconds, which depends on hardware. It answers: "if I double the input, roughly how much slower does this get?"

## 2. The Common Complexity Classes, Fastest to Slowest

![Growth curves from flattest to steepest: O(1), O(log n), O(n), O(n log n), O(n squared)](diagrams/01-big-o-growth-curves.svg)

| Notation | Name | Example | Doubling `n` roughly... |
|---|---|---|---|
| O(1) | constant | `arr[0]`, `map.get(key)` | ...changes nothing |
| O(log n) | logarithmic | binary search | ...adds one more step |
| O(n) | linear | a single loop over the array | ...doubles the time |
| O(n log n) | linearithmic | efficient sorting (`Array.sort`) | ...slightly more than doubles |
| O(n²) | quadratic | nested loop over the same array | ...quadruples the time |
| O(2ⁿ) | exponential | naive recursive Fibonacci | ...squares the time |

```js
function constant(arr) { return arr[0]; }                    // O(1)

function linear(arr) { for (const x of arr) console.log(x); } // O(n)

function quadratic(arr) {                                      // O(n²)
  for (const a of arr) for (const b of arr) console.log(a, b);
}
```

## 3. Why Constants and Lower-Order Terms Are Dropped

```js
function example(arr) {
  console.log(arr[0]);       // O(1)
  for (const x of arr) {}    // O(n)
  for (const x of arr) {}    // O(n) — a second, separate loop
}
// Total: O(1) + O(n) + O(n) = O(2n + 1)
// Big-O drops constants and lower-order terms -> simplifies to O(n)
```

Big-O describes **growth trend**, not an exact operation count — `O(2n)` and `O(n)` belong to the same complexity class because they scale identically as `n → ∞`.

## 4. Nested Loops Multiply, Sequential Loops Add

```js
function nested(arr) {          // O(n * n) = O(n²) — loops MULTIPLY when nested
  for (const a of arr) for (const b of arr) {}
}

function sequential(arr) {       // O(n + n) = O(n) — loops ADD when sequential, simplifies away
  for (const a of arr) {}
  for (const b of arr) {}
}
```

## 5. Analyzing Real Array Method Costs

| Operation | Complexity | Why |
|---|---|---|
| `arr[i]` (index access) | O(1) | direct memory offset |
| `arr.push()` / `arr.pop()` | O(1) amortized | operates at the end only |
| `arr.shift()` / `arr.unshift()` | O(n) | every remaining element must shift index |
| `arr.includes()` / `arr.indexOf()` | O(n) | must scan until found (or not) |
| `arr.sort()` | O(n log n) | comparison-based sort |
| `map.get(key)` / `set.has(value)` | O(1) average | hash table lookup (see Hashing topic) |

```js
const arr = [1, 2, 3, /* ...huge array... */];
arr.unshift(0); // O(n) — every other element's index shifts up by one, internally
arr.push(0);     // O(1) — no shifting needed, just appends at the end
```

Continue to `js_time_and_space_complexity_theory_2.md` for space complexity and worked examples.