Big-Theta Notation

complexity-theory

Definition

Big-Theta Notation

Let be functions. We say that is Big-Theta of , written

if is bounded above and below by constant multiples of :

Meaning

Big-Theta notation gives an asymptotically tight bound. It says that and have the same growth rate up to constant factors.

Equivalently,

Example

Tight quadratic bound

Let

Then

because is bounded above and below by constant multiples of for all sufficiently large .