Definition:Asymptotically Tight Bound

From ProofWiki
Jump to navigation Jump to search


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$.