Notation for Asymptotic and Runtime Analysis
Here we collect notation related to asymptotic notation and runtime analysis of algorithms.
Asymptotic Notation
| Notation | Meaning |
| $g(N)$ is $O(f(N))$ | There exists constant $c > 0$ and $N_0 > 0$ such that for every $N\ge N_0$, we have $g(N)\le c\cdot f(N)$ |
| $g(N)$ is $\Omega(f(N))$ | There exists constant $\epsilon > 0$ and $N_1 > 0$ such that for every $N\ge N_1$, we have $g(N)\ge \epsilon\cdot f(N)$ |
| $g(N)$ is $\Theta(f(N))$ | $g(N)$ is $O(f(N))$ and $g(N)$ is $\Omega(f(N))$ |
Runtime Analysis
| Notation | Meaning |
| $N$ | Size of the input $N$ (not be equated with $n$ every time e.g. for Stable Matching Problem) |
| $T_A(N)$ | Maximum runtime of algorithm $A$ over all inputs of size of the input $N$. When $A$ is clear from the context, we will drop it from the subscript. |