Choosing a $c$ and $n_0$ that shows that $f(n) \in O(g(n))$ or $\Omega(g(n))$?

28 Views Asked by At

How do you accurately select a $c$ or $n_0$ value that would effectively prove these cases?

For example, if you had $f(n) = log_3(n)$ and $g(n) = log_9(n)$, how would you know to select $c = 1$ and $n_0 = 2$ to prove that $f(n) \in O(g(n)$?

Similarly, if you had $f(n) = 3n+n log(n)$ and $g(n) = (5 log(n))$, how would you know to select $c = 1$ and $n_0 = 2$ to prove that $f(n) \in \Omega(g(n)$?

From the way that I have seen such proofs demonstrated, you are meant to select $c$ and $n_0$ first before beginning your proof, and then retroactively prove that those values satisfy the definitions of $O(n)$ and $\Omega(n)$.

It is not clear to me how to accurately and effectively select these values without randomly guessing.