big Theta notation

A way of writing an exact growth rate: Theta(f(n)) means the cost is both O(f(n)) and Omega(f(n)).

In more detail

Theta pins the cost between two constant multiples of the same function, so it states the true rate rather than just a ceiling. The worst case of linear search is Theta(n), since in the worst case every element must be checked and no more. Engineers often say O when they mean Theta; the course keeps them separate so each claim is precise.

Related terms

Taught in

References