This notation bounds a function to in constant factors. We say f(n) = Θ(g(n)) if there presents positive constants n0, c1 and c2 such that to the right of n0 the value of f(n) always lies between c1g(n) and c2g(n), both inclusive. The given Figure gives an idea about function f(n) and g(n) where f(n) = Θ(g(n)) . We will say that the function g(n) is asymptotically tight bound for f(n).
Figure: Plot of f(n) = Θ(g(n))
For instance, let us show that the function f(n) = (1/3) n2 - 4n = Θ(n2).
Now, we must determined three positive constants, c 1, c 2 and no as
c1n2 ≤1/3 n2 - 4n ≤ c2 n2 for all n ≥ no
⇒ c1 ≤ 1/3- 4/n ≤ c2
By choosing no = 1 and c2 ≥ 1/3 the right hand inequality holds true.
Likewise, by choosing no = 13, c1 ≤ 1/39, the right hand inequality holds true. Thus, for c1 = 1/39 , c2 = 1/3 and no ≥ 13, it follows that 1/3 n2 - 4n = Θ (n2).
Surely, there are other alternative for c1, c2 and no. Now we might illustrates that the function f(n) = 6n3 ≠ Θ (n2).
In order to prove this, let us suppose that c3 and no exist such that 6n3 ≤ c3n2 for n ≥ no, But this fails for adequately large n. Therefore 6n3 ≠ Θ (n2).