The theta notation essentially means "about the same as."
It is considered the intersection of the Big-O and Big-Omega of a function.
For instance if you have a function F which is O(G) and Omega(G) then it is said to be Theta(G). F is O(G) means there is a real number \(\displaystyle \epsilon\) such that \(\displaystyle \epsilon\)G \(\displaystyle \ge\) F for some input size cutoff i.e. for large natural numbers n, \(\displaystyle \epsilon\)G performs worse than F.
Similarly, F is Omega(G) means there is a real number \(\displaystyle \delta\) such that \(\displaystyle \delta\)G \(\displaystyle \le\) F for some input size cutoff i.e. for large natural numbers n, \(\displaystyle \delta\)G performs better than F.
For a quick example, consider the functions f(n)=n<sup>2</sup> and g(n)=3n<sup>2</sup>.
f(n) is O(g(n)) because with \(\displaystyle \epsilon\)=1, \(\displaystyle f(n) \le\) \(\displaystyle \epsilon g(n)\). It is also Omega(g(n)) since \(\displaystyle \delta = \frac{1}{4}\) satsifies f(n) \(\displaystyle \ge \delta g(n)\). Therefore f(n) is Theta(g(n)).
There is also a calculus-based technique. take \(\displaystyle \L {lim}_{_{n \rightarrow \infty}} \frac{f(n)}{g(n)}\). If L is a constant number then f(n) is Theta(g(n). If it is zero then f(n) = O(g(n)). If it is infinity, then f(n)=Omega(g(n)).
