Question

This is a question about big theta notation. So, Θ(g(n)) is the set of functions where

Θ(g(n))={f(n): there exists positive constants c_1, c_2, and n_0 such that 0 <= c_1g(n) <= f(n) <= c_2g(n) for all n >= n_0}

Why does this constraint exist?

0 <= c_1g(n) <= f(n) <= c_2g(n) for all n >= n_0

Where do they get the c_1g(n) from?

Answer 1

Theta is a combination of Omega and O.

Answer 2

They basically combined definitions. The purpose of the \(c_1g(n)\) is to ensure that is it \(f(n)\in \Omega(g(n))\) as well.