Big Theta Notation - Average case

The theta notation bounds a functions from above and below, so it defines exact asymptotic behavior.A simple way to get Theta notation of an expression is to drop low order terms and ignore leading constants. For example, consider the following expression.

3n^3 + 6n^2 + 6000 = Θ(n^3)
Dropping lower order terms is always fine because there will always be a n0 after which Θ(n^3) has higher values than Θ(n^2) irrespective of the constants involved.

This is also called as Asymptotically equal, meaning the dominating term from f(n) can be taken as g(n). So in the above case its n^3.

f(n) = Θ (g(n))

c1 g(n) <= f(n) <= c2 g(n) for n>=n0, c1, c2 > 0, n0 >=1

example:

f(n) = 3n+2, g(n) = n

c1 = 1, c2 = 4 and n0 >= 1