78 lines
2.7 KiB
Markdown
78 lines
2.7 KiB
Markdown
---
|
|
date: 02.09.2024
|
|
type: theoretical
|
|
---
|
|
|
|
|
|
$\mathcal{O}$
|
|
|
|
## Complexity
|
|
- Time Complexity: amount of time an algorithm takes to complete as a function of the size of its input.
|
|
- Space Complexity: amount of memory it uses as a function of the size of its input.
|
|
|
|
### Big O
|
|
- **Formal Definition:**
|
|
|
|
Big O notation, $\mathcal{O}(f(n))$, describes the upper bound of the time or space complexity of an algorithm in terms of the input size $n$. It characterizes the worst-case scenario of an algorithm's growth rate.
|
|
|
|
Formally, a function $T(n)$ is said to be $\mathcal{O}(f(n))$ if there exist positive constants $c$ and $n_0$ such that for all $n \geq n_0$:
|
|
|
|
$$
|
|
0 \leq T(n) \leq c \cdot f(n).
|
|
$$
|
|
|
|
This means that $T(n)$ will grow at most as fast as $f(n)$, up to a constant multiple $c$, for sufficiently large $n$.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
### Informally:
|
|
Big-O notation provides an upper limit on:
|
|
- **Time**: How long an algorithm will take.
|
|
- **Space**: How much memory it will require.
|
|
It helps compare algorithms by focusing on their growth rate and ignoring constant factors.
|
|
|
|
|
|
### Other Notations for Growth Rates
|
|
|
|
1. **Big-O ($\mathcal{O}(f(n))$)**:
|
|
- Describes the **upper bound** (worst-case) of $T(n)$.
|
|
- Informally: $T(n)$ grows no faster than $f(n)$.
|
|
- Formal Definition:
|
|
$$
|
|
T(n) \text{ is } \mathcal{O}(f(n)) \iff \exists c > 0, n_0 > 0 \text{ such that } T(n) \leq c \cdot f(n) \text{ for all } n \geq n_0.
|
|
$$
|
|
|
|
2. **Big-Omega ($\Omega(f(n))$)**:
|
|
- Describes the **lower bound** (best-case) of $T(n)$.
|
|
- Informally: $T(n)$ grows at least as fast as $f(n)$.
|
|
- Formal Definition:
|
|
$$
|
|
T(n) \text{ is } \Omega(f(n)) \iff \exists c > 0, n_0 > 0 \text{ such that } T(n) \geq c \cdot f(n) \text{ for all } n \geq n_0.
|
|
$$
|
|
|
|
3. **Big-Theta ($\Theta(f(n))$)**:
|
|
- Describes the **exact bound** (tight bound) of $T(n)$.
|
|
- Informally: $T(n)$ grows exactly as fast as $f(n)$.
|
|
- Formal Definition:
|
|
$$
|
|
T(n) \text{ is } \Theta(f(n)) \iff T(n) \text{ is } \mathcal{O}(f(n)) \text{ and } T(n) \text{ is } \Omega(f(n)).
|
|
$$
|
|
|
|
4. **Little-O ($o(f(n))$)**:
|
|
- Describes a **loose upper bound** of $T(n)$.
|
|
- Informally: $T(n)$ grows strictly slower than $f(n)$.
|
|
- Formal Definition:
|
|
$$
|
|
T(n) \text{ is } o(f(n)) \iff \forall c > 0, \exists n_0 > 0 \text{ such that } T(n) < c \cdot f(n) \text{ for all } n \geq n_0.
|
|
$$
|
|
|
|
Think of growth rates as vehicles on a highway:
|
|
- $\mathcal{O}(f(n))$: $T(n)$ cannot go faster than $f(n)$.
|
|
- $\Omega(f(n))$: $T(n)$ cannot go slower than $f(n)$.
|
|
- $\Theta(f(n))$: $T(n)$ moves at the exact same speed as $f(n)$.
|
|
- $o(f(n))$: $T(n)$ moves slower than $f(n)$ and never catches up.
|
|
|