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
- Big O notation — A way of writing an upper bound on growth: O(f(n)) means the cost grows no faster than a constant times f(n) for large n.
- big Omega notation — A way of writing a lower bound: Omega(f(n)) means the cost grows at least as fast as a constant times f(n) for large n.
Taught in
- Big O, Big Omega And Big Theta — Algorithms & Data Structures for Working Engineers