Classical notations like \(O\), \(\Omega\), and \(\Theta\) describe the growth rate of a single function. However, modern system architectures (AI pipelines, microservices, caching layers) require a structural guarantee that an upstream layer never exceeds a downstream layer. The \(\psi\) (Psi) notation fills this gap by introducing ordered asymptotic bounds for pairs of sequential functions.
Let \(F_1, F_2 : \mathbb{N} \to \mathbb{R}^+\) be a pair of non-negative functions. The ordered pair \((F_1, F_2)\) belongs to the complexity class \(\psi(g(n))\) if there exist positive constants \(c_1, c_2, c_3\) such that for all sufficiently large \(n\):
Interpretation: The term \(c_2 \cdot g(n)\) acts as a "bridge". It guarantees that \(F_1\) is asymptotically bounded above by \(F_2\), ensuring a safe, unidirectional data flow without heuristic thresholds.
By substituting \(g(n)\) with common growth functions, \(\psi\) yields specific ordered classes:
| Notation | Growth Rate | Ideal Application |
|---|---|---|
| \(\psi(1)\) | Constant | Real-time systems, fixed-latency hardware |
| \(\psi(\log N)\) | Logarithmic | Binary search, B-Tree indexing |
| \(\psi(N)\) | Linear | Data streaming, ETL pipelines |
| \(\psi(N \log N)\) | Log-Linear | Sorting (Merge Sort, Quick Sort) |
| \(\psi(N^2)\) | Quadratic | Nested loops, certain DP algorithms |
This notation was born from a concrete engineering problem in two-tier architectures:
"How do we mathematically guarantee that the retriever (Fโ) doesn't flood the generator (Fโ) with more requests than it can handle?"
\(\psi\) provides a rigorous proof that \(F_1 \le F_2\) asymptotically, eliminating the need for fragile heuristic overload protection in critical systems.
Download the complete 2-page PDF defining the \(\psi\) notation.
Download ฯ.pdf (Formal Paper)๐ Pastikan file psi.pdf sudah ada di folder yang sama.
Source code, raw LaTeX definitions, and this website are available on GitHub: