Definition:Asymptotically Tight Bound
Jump to navigation
Jump to search
Definition
Let $f$ and $g$ be real-valued functions.
Let $f$ and $g$ be such that:
- $f \in \map \Theta g$
where $\Theta$ denotes $\Theta$ notation.
That is:
- $\exists c_1, c_2 \in \R: \exists n_0 \in \Dom f: \forall n \ge n_0: c_1 \map g n \le \map f n \le c_2 \map g n$
That is, $f$ is equal to $g$ within a constant factor when $n$ is sufficiently large.
Then $\map g n$ is an asymptotically tight bound for $\map f n$.
Sources
- 1990: Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest: Introduction to Algorithms ... (previous) ... (next): $2$: Growth of Functions: $2.1$ Asymptotic Notation: $\Theta$-notation