Asymptotic notation
Definitions
T(N) = \mathcal{O}(f(N)) if there are positive constants c and n_0 such that T(N) \leq cf(N) when N \geq n_0. This is an upper bound.
T(N) = \Omega(g(N)) if there are positive constants c and n_0 such that T(N) \geq cg(N) when N \geq n_0. This is a lower bound.
T(N) = \Theta(h(N)) if and only if T(N) = \mathcal{O}(h(N)) and T(N) = \Omega(h(N)). This is a tight bound.
T(N) = \mathcal{o}(p(N)) if for all positive constants c there exists some n_0 such that T(N) < cp(N) when N > n_0. This is a strict upper bound.
Example
Let f(N) = N^2. Then, T(N) = \mathcal{O}(N^2) if there are positive constants c and n_0 such that T(N) \leq cN^2 when N \geq n_0.
Copyright 漏 2023鈥�2025 Clayton Cafiero
No generative AI was used in producing this material. This was written the old-fashioned way.