时间复杂度分析统计的不是算法运行时间，**而是算法运行时间随着数据量变大时的增长趋势**
| Big-O | How to Say It | Meaning / When It Appears |
| ------------ | ----------------------------- | ----------------------------------------- |
| `O(1)` | “O of one” or “constant time” | Accessing array index, hashmap get/put |
| `O(log n)` | “O of log n” | Binary search, balanced trees |
| `O(n)` | “O of n” | One-pass loops, two pointers, prefix sums |
| `O(n log n)` | “O of n log n” | Sorting (merge sort, quicksort) |
| `O(n^2)` | “O of n squared” | Double loops, brute force, 2D DP |
| `O(n^3)` | “O of n cubed” | Tripple loops |
| `O(2^n)` | “O of two to the n” | Backtracking (subsets, combinations) |
| `O(n!)` | “O of n factorial” | Full permutations of n elements |
## Common Time Complexity Scenarios (with pronunciation)
### `O(1)` — Constant Time
**Description**: Execution time does **not grow** with input size.
**Examples**:
1. Array index access (`arr[i]`)
2. HashMap insert and lookup (average case)
3. Stack push and pop
### `O(log n)`
**Description**: Time grows **logarithmically** with input size.
**Examples**:
1. Binary search
2. Operations on balanced BSTs (e.g. AVL, Red-Black Tree)
3. Some divide and conquer algorithms
### `O(n)` — Linear Time
**Pronounced**: “O of n”
**Description**: Time grows **linearly** with input size.
**Examples**:
1. Iterating through an array or linked list
2. Linear search
3. Calculating the sum or average of an array
### `O(n log n)` — Linearithmic Time
**Description**: Slightly slower than linear, but faster than quadratic.
**Examples**:
1. Efficient sorting (merge sort, quicksort)
2. Heap operations (e.g. heap sort)
3. Some divide and conquer algorithms
### `O(n²)` — Quadratic Time
**Pronounced**: “O of n squared”
**Description**: Time grows with the **square of input size**.
**Examples**:
1. Nested loops
2. Simple sorts like bubble sort and selection sort
3. Generating all possible pairs
### `O(2ⁿ)` — Exponential Time
**Pronounced**: “O of two to the n”
**Description**: Time **doubles** with each additional input element.
**Examples**:
1. Recursive Fibonacci
2. Generating all subsets
3. Brute-force solution to the Traveling Salesman Problem
### `O(n!)` — Factorial Time
**Pronounced**: “O of n factorial”
**Description**: Time grows **factorially** with input size.
**Examples**:
1. Generating all permutations
2. Brute-force solution to the Traveling Salesman Problem